[백준/DP] 11727번 2xn 타일링 2 (JAVA)

문제

---

풀이

2xn 타일링 기본 문제와 다른 점은 2x2 타일이 추가됐다는 점이다.

앞선 문제에서 이전(i-2번째) 타일 맨 끝에 추가로 2x2 범위에 타일을 채울 때, 1x2 타일을 2개 이어 붙이는 한 가지 방식만 가능했다. 하지만 이번 문제에서는 2x2 타일이 추가로 주어지기 때문에, 1x2 타일을 2개 이어 붙이거나, 2x2 타일 하나를 이어 붙이는 두 가지 방식이 가능해졌다.

따라서 점화식이 dp[i] = dp[i-1] + 2 * dp[i-2]로 변경된다.

코드

import java.io.*;

public class Main {

    private static final int MAXIMUM = 1000;
    private static final int MOD = 10007;

    private static int n;
    private static int[] dp = new int[MAXIMUM + 1];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        dp();
        bw.append(String.valueOf(dp[n]));

        br.close();
        bw.close();
    }

    private static void dp() {
        dp[1] = 1;
        dp[2] = 3;
        for (int i = 3; i <= n; i++)
            dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % MOD;
    }
}