[백준11727번] 2xn타일링 2

문제

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

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

입력

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

출력

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

예제 입력 1 복사

2

예제 출력 1 복사

3

예제 입력 2 복사

8

예제 출력 2 복사

171

예제 입력 3 복사

12

예제 출력 3 복사

2731

나의풀이

처음에는 마지막의 타일에 대해 2*1 타일이 왼쪽과 오른쪽에 붙는 경우들에 대하여 생각을 해보았다. 그러나 그렇게는 쉽게 문제가 해결되지 않아 그림을 그려보다가 다이나믹프로그래밍 기법 문제인 것을 생각하고는 앞에 구해놓은 것을 어떻게 활용하면 좋을까하다가 n이 1씩 증가할때마다 바로 앞에서 구한 모든 n-1의 경우 맨 뒤에 2x1의 타일을 붙이고 맨 뒤에 2x2타일이 오는 경우를 추가해주면 되겠다는 생각이 들었다.

따라서 아래와 같은 점화식을 구할 수 있었다.

dp[n] = dp[n-1] +( 2 * dp[n-2] )

아래는 생각을 그림으로 그려본 것이다.

코드

import java.util.Scanner;

/**
 * 11727번 2xn타일링2
 */
public class Baeckjun11727 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] dp = new int[n+1];

        for (int i=1; i<=n; i++) {
            if (i==1) dp[1] = 1;
            else if (i==2) dp[2] = 3;
            else dp[i] = (2*dp[i-2] + dp[i-1]) % 10007;
        }

        System.out.println(dp[n]);
    }
}