[AJ/DP] 직사각형 배치의 경우의 수

문제

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

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

입력

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

출력

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

예제 입력

3

예제 출력

3

예제 입력

8

예제 출력

34

예제 입력

37

예제 출력

87896

---

풀이

N = 1 일 때 1개

N = 2 일 때 2개

N = 3 일 때 3개

N = 4 일 때 5개

.....

이렇게 하나 씩 구하다보면 점화식을 구할 수 있다.

data[n] = data[n-1] + data[n-2] 

 

(이 문제를 DP로 풀어라하면 쉽게 풀 수 있지만, 이 문제를 딱 보고 DP로 풀어야겠다라고 생각하는 것이 쉽지않다..)

코드

import 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 data[] = new int[n+1];
        data[1] = 1;
        data[2] = 2;
        for(int i=3;i<=n;i++) {
            data[i] = (data[i-1] +data[i-2])%1000007;
        }
        System.out.println(data[n]);

    }

}