백준 다이나믹 알고리즘 - 2xn 타일링 11726번

---

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

---

 

package dynamic;
 
import java.util.Scanner;
 
public class TilingX2_11726 {
 
    //여기서 아이디어는 도형을 실제 만들어보면 
    //d[4]는 d[2]에 1*2(가로로 긴 사각형)를 2개 더한것과 d[3]에 2*1(세로로 긴 사각형) 1개를 더한것과 합이 같다.
    //즉 d[i] = d[i-1] + d[i-2]이다.
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
 
        //d의 크기는 1001개로 설정해준다. 여기서 1001개로 설정 한 이유는 n이 1<=n<=1000 이기 때문이다.
        int[] d = new int[1001];
 
        //d[2]를 시작하려면 d[2-2], d[2-1]이 필요하므로 d[0]과 d[1]를 먼저 선언해준다.
        d[0] = 1;
        d[1] = 1;
 
        //점화 식을 통해 d[i]를 구한다.
        for (int i = 2; i <= n; i++) {
            d[i] = d[i - 1] + d[i - 2];
            //여기서 10007은 소수이다. 10007로 나눈 나머지를 저장하지 않으면 자료형의 크기를 넘을 수 있기 때문에
            //백준에서 런타임 에러를 방지하고자 10007로 나누는 것이다.
            d[i] = d[i] % 10007;
            
        }
        System.out.println(d[n]);
    }
 
}