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

예제 입력

4

예제 출력

7

 

예제 입력

200

예제 출력

290816

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class makenum {
    /**
     *
     * 숫자 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 로 나눈 나머지를 출력한다.
     *
     * @param args
     */


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        long[] dpCount = new long[N+1+3];

        dpCount[1] = 1;
        dpCount[2] = 2;
        dpCount[3] = 4;

        for (int i=4; i<=N; i++){
            dpCount[i] = dpCount[i-1] + dpCount[i-2] + dpCount[i-3];
            dpCount[i] %= 1000007L;
        }

        System.out.println(dpCount[N]);

    }

}