숫자 만들기

숫자 만들기

 

문제

---

숫자 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.util.*;

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();
    public static long finalResult = 0;

    //    public static long max = Integer.MIN_VALUE;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        long b[];
        long c;
        int d[];
        int count = 0;
        long max = Integer.MIN_VALUE;
        a = sc.nextInt();

        b = new long[a + 1];
        b[1] = 1;
        b[2] = 2;
        b[3] = 4;

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

        System.out.println(b[a]);


        sc.close();

    }


}