백준 15990 - 1,2,3 더하기 5

 

전에 풀었던 1,2,3 더하기 업그레이드 버전이다. 같은 수를 중복하지않은 1,2,3 더하기를 만들면된다.

 

여기서 중복, 감소, 증가라는 단어를 살펴보면

1,1,2,3,4,3,2,1 -> 수를 바로 옆과 비교해서 두개씩 끊어서 생각해보면 된다.

1,1중복 -> 1,2중복x 증가 -> 2,3증가 ->3,4증가->4,3감소 계속 양 옆을 비교하는 것이다.

 

이제 문제로 돌아가보자. 문제에서는 중복되는 경우의 수를 제거하고 1,2,3을 사용해서 숫자를 만드는 경우의 수를 찾고 싶다.

 

예시 처럼 4를 만들고자 한다면, 3+1, 1+3,1+2+1의 꼴로 만드는 것이다.

먼저 그냥 1,2,3 더하기 처럼 생각해보자 N이라는 숫자를 만드는 경우의 수는 다음과 같다.

N = N-1 +1

      N-2 +2   각각 마지막 수까지 만드는 경우의 수에 1,2,3을 마지막으로 더해주는 꼴이다.

      N-3 +3

여기서 중복을 제거한다면 어떻게 해야할까? 

마지막에 1을 더해서 만들었다면, N-1을 만들 때 2와 3을 마지막으로 사용해서 만들었어야 했을 것이다.

마지막에 2를 더해서 만들었다면, N-2를 만들 때 마찬가지로 1이나 3을 마지막으로 사용해서 만들었어야 했을 것이다.

3도 이와 마찬가지일 것이다. 

따라서 수를 만들 때 각각 마지막의 사용한 숫자까지 생각하여 경우의 수를 따로따로 쪼개서 저장한 다음에 

N을 만들때 마지막으로 1을 사용한 경우 2를 사용한 경우 3을 사용한 경우를 더 해주면 된다.

 

만들려는 숫자를 n 마지막의 사용한 숫자를 i라고 하면,

그냥 1,2,3더하기에서는 d[n] = d[n-1]+d[n-2]+d[n-3]로 마지막에 올 수 있는 1,2,3에 따라 각 수가 만들어지는 경우의 수를 하나로 저장했다면 이제는 

d[n][1] = 1을 사용한 경우의 수 따로 d[n][2] = 마지막으로 2를 사용한 경우의 수 따로 , d[n][3] 마지막에 3을 사용한 경우의 수를 따로 따로 저장한 다음 

d[n][1] = d[n-1][2] + d[n-1][3]

d[n][2] = d[n-2][1] + d[n-2][3]

d[n][3] = d[n-3][1] + d[n-3][2] 로 쪼개서 경우의 수를 저장해서 d[n]을 구하는 것이다.

 

4를 예시로 들어본다면,

먼저 d[1][1] =1, d[1][2]=0. d[1][3]=0 1은 마지막 수로 2와 3을 사용할 수 없음으로 d[1][1] = 1개

     

        d[2][1] = d[1][2] + d[1][3] = 0 --마지막 수로 1을 사용 d[1][1]은 올 수 없다 d[1][1]->1+1 < d[2][1] 로 만들면 중복

        d[2][2] = d[0][1] + d[0][3] = 1 -- 0을 1이나 3으로 만드는 경우의 수는 없다. 하지만  2로 2를 만들 수 있으므로 1개 

     

       d[3][1] = d[2][2] +d[2][3] = 1개

       d[3][2] = d[1][1] + d[1][3] = 1개  

       d[3][3]  = 1개  3으로 3을 만들 수 있다.

 

      d[4][1] = d[3][2]+d[3][3] = 2개 

->그냥 1,2,3만들기에서는  3을 만드는 경우의 수 모두가 필요했다면, 지금은 3을 만들면서 2로 끝나는 경우와 3으로 끝          나는 경우만 필요하다 

      d[4][2] = d[2][1]+d[2][3] = 0개

      d[4][3] = d[1][1] +d[1][2] =1개 

따라서 d[4]를 만드는 경우의 수는 1로 끝날때 2개 2로 끝나면 0개 3으로 끝나면 1개로 총 3가지 경우만 가능하다.

실제로도 3+1, 1+3, 1+2(3을 만들면서 2로끝나는 경우) +1로 총 3개이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
    public static long[][] d;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        final long mod = 1000000009L;
        final int MAX = 100000;
        d = new long[MAX+1][4];
        d[1][1] =1;
        d[1][2] =0;
        d[1][3] =0;

       for(int i=1; i<=MAX;i++){
           for(int j=1; j<=3 ;j++){
               if(j==1){
                   if(i>1){
                       d[i][j] =d[i-j][2]+d[i-j][3];
                   } else if (i==1) {
                       d[i][j] =1;
                   }
                   d[i][j] %= mod;
               }if(j==2){
                   if(i>2){
                       d[i][j] =d[i-j][1]+d[i-j][3];
                   } else if (i==2) {
                       d[i][j] =1;
                   }
                   d[i][j] %= mod;
               }if(j==3){
                   if(i>3){
                       d[i][j] =d[i-j][1]+d[i-j][2];
                   } else if (i==3) {
                       d[i][j] =1;
                   }
                   d[i][j] %= mod;

               }
           }
       }
       while(t -- >0) {
           int result = 0;
           int n = Integer.parseInt(br.readLine());
           System.out.println((d[n][1] + d[n][2] + d[n][3])%mod);

       }

        }



    }

문제에서 원하는 %mod를 제외하고 

for문에서 예외처리한 부분은 

 

d[1][1]d[2][2]d[3][3] 을 처리해주기 위해 각각의 i,j가 1,1일 때 1.. 2,2일때 1 3,3일때 1을 넣어준것이다.