[백준 알고리즘] 11727번 : 2×n 타일링 2

문제

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

입력

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

출력

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

코드

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

public class BOJ_11727 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] dp = new int[N + 2];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 3;

        for (int i = 3; i <= N; i++) {
            dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
        }
        System.out.println(dp[N]);
    }
}

풀이 및 느낀점

dp를 이용하여 문제에 접근했다.

2x1, 1x2, 2x2 타일이 존재한다. 이때, 배열의 맨 마지막을 채우는 방식으로 dp 점화식을 세웠다.

1x2를 사용하면 dp[n-1]을 어떻게 채울지가 중요하다.
2x1을 사용하면 dp[n-2]를 어떻게 채울지가 중요하다.
2x2를 사용하면 dp[n-2]를 어떻게 채울지가 중요하다.

결론적으로 2x1을 사용해서 채울 때와 2x2를 사용해서 채울 때는 동일한 케이스에 해당된다. 따라서 점화식을 만들때 dp[n-2]를 2번 더해준다.

최종적인 점화식은 dp[n] = dp[n-1] + dp[n-2]*2 이다.

참고자료