[동적계획법 (D.P.)] 백준 11727: 2 x N 타일링 2, Java

1. 접근

단순하게 생각했을 때 새로운 n번째 타일을 채울 때는 n - 1번째 타일들에

세로 직사각형 1개가 추가되는 것을 생각할 수 있었습니다.

나머지 경우의 수를 생각해보았을 때 방금 추가한 세로 직사각형이 중간에 들어갈 수 있기 때문에

상상만으로 접근하기에는 어려웠습니다.

 

2. 해결

그림을 그려 규칙을 찾아보는 것으로 하였습니다.

 

2 x 1

 

2 x 2

 

2 x 3

- 2 x 2 타일에 세로 직사각형 타일 추가

- 2 x 1 타일에 가로 두 개 타일, 정사각형 타일 추가

 

2 x 4

- 2 x 3 타일에 세로 직사각형 타일 추가

- 2 x 2 타일에 가로 두 개 타일, 정사각형 타일 추가

 

즉 n번째 타일의 경우의 수는

(n - 1번째 타일의 경우의 수) + (n - 2번째 타일의 경우의 수의 두 배)

 

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int[] dp = new int[n + 1];

        dp[0] = 1;
        dp[1] = 1;

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

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