[Baekjoon Online Judge] 11727번: 2xn 타일링 2

11727번: 2×n 타일링 2

요구사항

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

입력

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

출력

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

---

2021/01/30 - [문제 풀이/다이나믹 프로그래밍] - [Baekjoon Online Judge] 11726번: 2xn 타일링

[Baekjoon Online Judge] 11726번: 2xn 타일링

 앞서 풀었던 2xn 타일링 문제에 추가적인 조건이 더 붙은 문제이다. 앞선 문제에서는 쉽게 점화식을 구할 수 있었다. 타일링 2에서는 추가적으로 2 x 2 타일이 추가되었기 때문에 다른 점화식으로 나타낼 수 있다.

 

 간단하게 그림으로 표현해보았다.

 

 

 즉 2 x 2 타일을 두 가지 형태로 표현이 가능하기 때문에 x 2를 해주어 표현한다.

 

f(1) = 1
f(2) = 3
f(n) = f(n - 2) x 2 + f(n - 1)

 

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

public class Baekjoon11727 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bufferedReader.readLine()); // 1 <= n <= 1_000
        int[] dp = new int[n + 2];

        dp[1] = 1;
        dp[2] = 3;

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

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

        bufferedReader.close();
    }
}