10-6: 직사각형 배치의 경우의 수

직사각형 배치의 경우의 수

 

문제

---

2 x N 직사각형 모양의 칸이 있다. 이를 2 x 1 모양의 타일로 가득 채우려 한다. 가능한 경우의 수를 출력하는 프로그램을 작성하시오. 단, 가능한 경우의 수가 매우 많을 수 있으므로, 그 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

예를 들어, N = 3 일 경우에는 다음 세 가지의 가능한 경우가 존재한다.

 

입력

---

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

출력

---

가능한 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

 

예제 입력

3

예제 출력

3

 

예제 입력

8

예제 출력

34

 

예제 입력

37

예제 출력

87896

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

public class dp_rect_placement {

    /**
     * 직사각형 배치의 경우의 수
     *
     *
     * 문제
     * 2 x N 직사각형 모양의 칸이 있다. 이를 2 x 1 모양의 타일로 가득 채우려 한다. 가능한 경우의 수를 출력하는 프로그램을 작성하시오. 단, 가능한 경우의 수가 매우 많을 수 있으므로, 그 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.
     *
     * 예를 들어, N = 3 일 경우에는 다음 세 가지의 가능한 경우가 존재한다.
     *
     * 첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100 )
     *
     * 출력:
     * 가능한 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.
     *
     * 예제 입력:
     *
     * 8
     *
     *
     * 예제 출력:
     * 34
     *
     *
     * 37
     * 87896
     *
     * @param args
     */

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

        int dp[] = new int[N+1];

        dp[1] = 1;
        dp[2] = 2;

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

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

    }
}