[필수 문제] 숫자 만들기

1. 문제

숫자 1, 2, 3을 이용하여 숫자 N을 만드는 경우의 수를 출력하는 프로그램을 작성하시오. 예를 들어, N이 4일 경우에는 다음의 7가지 경우가 존재한다. 단, 경우의 수가 매우 많을 수 있으므로, 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

---

입력

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 

출력

1, 2, 3을 이용하여 N을 만들 수 있는 경우의 수를 1,000,007 로 나눈 나머지를 출력한다. 

예제 입력

case 1) 4

case 2) 200

예제 출력

case 1) 7

case 2) 290816

 

 

 

2. 풀이

숫자 만들기는 동적 계획법을 이용해야 해결이 가능한 문제이다.

 

동적 계획법에서 가장 중요한 요소는 과연 이 문제가 동적 계획법을 이용해야하는지 아닌지 판별하는 것이라고 생각한다. 우선 가장 중요한 패턴을 찾아보면 된다.

 

n = 4일 경우, 총 7개의 경우의 수가 나온다.

• 1 + 1 + 1 + 1
• 1 + 1 + 2
• 1 + 2 + 1
• 2 + 1 + 1
• 2 + 2
• 1 + 3
• 3 + 1

 

여기서 패턴은 한번에 찾기 힘들지만, 가장 마지막 요소가 동일한 것 끼리 묶어보면 힌트가 보인다.

1 + 1 + 1 + 1 1 + 2 + 1 2 + 1 + 1 3 + 1	1 + 1 + 2 2 + 2	1 + 3
3 + 1	2 + 2	1 + 3
n = 3인 경우의 수 = 4개	n = 2인 경우의 수 = 2개	n = 1인 경우의 수 = 1개
즉, T(4) = T(4 - 1) + T(4 - 2) + T(4 - 3)

이를 공식화한다면 T(i) = T(i - 1) + T(i - 2) + T(i - 3) + ... T(i - m)이 된다. 그리고 이 특징은 전형적인 피보나치 수 구하는 문제와 동일하다는 것을 확인할 수 있다. 이를 코드화하면 다음과 같다.

import java.io.*;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int n;
    private static int[] arr;

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());
        arr = new int[n+1];

        /*
        T(1) = 1 (1)
        T(2) = 2 (1+1, 2)
        T(3) = 4 (1+1+1, 1+2, 2+1, 3) = 끝이 1인 경우의 수(2) + 끝이 2인 경우의 수(1) + 끝이 3인 경우의 수(1)
        T(4) = 1 + 2 + 4 + 끝이 4인 경우의 수(1) = 7
         */
        arr[1] = 1;
        int sum = 0;
        for(int i = 2; i <= 3; i++) {
            sum += arr[i-1];
            arr[i] = sum + 1;
        }

        for(int i = 4; i <= n; i++) {
            for(int j = i-3; j <= i-1; j++) {
                arr[i] = (arr[i] + arr[j]) % 1000007;
            }
        }
        
        bw.write(arr[n] + "");

        br.close();
        bw.flush();
        bw.close();
    }

}