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

https://althoughh.tistory.com/51

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

위에 먼저 풀고 이번 문제를 푸는 것을 추천한다.

이번 문제는 위의 문제의 활용이다.

또한 해당 유형의 문제가 익숙하지 않으면 그림을 한번 그려보는 것도 좋다.

 

---

문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

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

출력

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

---

 

package dynamic;
 
import java.util.Scanner;
 
public class TilingX2_11727 {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
 
        int[] d = new int[1001];
 
        d[0] = 1;
        d[1] = 1;
 
        //그림을 그려보면 d[n-2]에 뒤에 2*2의 정사각형 타일이 붙을수도 있고 1*2의 가로로 긴 사각형이 2개 붙을 수도 있다.
        //그래서 d[i-2]에 2를 곱해준다.
        for (int i = 2; i <= n; i++) {
            d[i] = d[i - 1] + (2 * d[i - 2]);
            //런타임 에러를 막기 위해 10007을 나눈 나머지를 구한다.
            //10007은 소수로 알고리즘 문제에서 많이 이용되는 소수이다.
            d[i] = d[i] % 10007;
        }
        System.out.println(d[n]);
 
    }
 
}