[AJ/DP] 숫자 만들기

문제

---

숫자 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 로 나눈 나머지를 출력한다.  

예제 입력

4

예제 출력

7

예제 입력

200

예제 출력

290816

---

풀이

n	경우의 수	count[i]
1	1	1
2	1+1 2	2
3	1+1+1 1+2 2+1 3	4
4	1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1	7 = count[1] +count[2] + count[3]
5	1+1+1+1+1  1+1+1+2 1+1+2+1 1+2+1+1 2+1+1+1 2+2+1 2+1+2 1+2+2 1+1+3 1+3+1 3+1+1 2+3 3+2	13 = count[2] +count[3] +count[4]
...	...	...
n	...	count[n-3] + count[n-2] + count[n-1]

DP의 풀이법을 적용하여

1. n=1,2,3은 초기화를 하고

2. 가장 작은 문제로 들어가서 답을 구한다.

    여기서는 4일 때 7개의 값을 구하고 5일 때 13값을 구하였다.

3. 점화식을 구하면 다음과 같다. 

  count[n-3] + count[n-2] + count[n-1]

코드

mport java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count[]= new int[n+1];
        count[1] = 1;
        count[2] = 2;
        count[3] = 4;
        
        if(n>3) {
            for(int i=4;i<=n;i++) {
                for(int j=i-3;j<=i-1;j++)
                    count[i]+=count[j];
                count[i] = count[i] %1000007;
            }
        }
        System.out.println(count[n]);
    }
}