2xn 타일링 2

문제

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

입력

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

출력

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

입력 2 -> 출력 3

입력 8 -> 출력 171

입력 12 -> 출력 2731

점화식

dp[i]는 폭 i인 2×i 직사각형을 세 종류의 타일로 채우는 방법 수다.

맨 오른쪽 열을 세로 2×1 타일로 채우면 남는 폭은 n-1이다. 마지막 두 열은 위아래 가로 1×2 타일 두 장으로 채우거나, 2×2 타일 한 장으로 채울 수도 있다. 이 둘은 서로 다른 배치이고 앞부분의 폭은 n-2다. 따라서 dp[n]=dp[n-1]+2×dp[n-2]가 된다.

맨 오른쪽 아래 칸에 놓인 타일의 모양으로 분류하면 세 경우가 모두 나온다. 세로 타일이면 오른쪽 한 열을 떼고, 가로 타일이면 위쪽 마지막 두 칸도 가로 타일이 차지해야 하며, 정사각형이면 마지막 두 열이 한 장으로 채워진다. 세 경우는 맨 오른쪽 아래 칸의 타일 종류가 달라 서로 겹치지 않는다. 마지막 부분을 제거한 나머지는 각각 임의의 2×(n-1) 또는 2×(n-2) 배치이므로 곱셈 계수 2가 생긴다.

빈 폭의 완성 상태 dp[0]=1, 폭 1의 세로 배치 dp[1]=1에서 시작한다. 폭 2에는 세로 두 장, 가로 두 장, 정사각형 한 장으로 3가지다. 폭 3은 dp[2]+2×dp[1]=5다. 2×dp[n-2]에서 2를 빠뜨리면 2×2 정사각형을 허용한 이 문제와 이전 11726번을 같은 문제로 계산하는 실수가 난다.

폭	마지막 세로	마지막 가로 두 장	마지막 정사각형	합계
2	`dp[1]=1`	`dp[0]=1`	`dp[0]=1`	3
3	`dp[2]=3`	`dp[1]=1`	`dp[1]=1`	5
4	`dp[3]=5`	`dp[2]=3`	`dp[2]=3`	11

폭 4에서는 마지막이 정사각형인 배치만 해도 왼쪽 폭 2를 채우는 세 방법마다 하나씩 생긴다. 실제 타일 배치를 전부 열거하지 않고도 부분 문제의 답을 재사용하는 이유다. 입력 예제의 폭 8도 이 표를 이어 계산하면 dp[5]=21, dp[6]=43, dp[7]=85, dp[8]=171이 된다.

n≤1,000이므로 각 단계에서 10007로 나누어 값을 유지한다. 코드의 시간 O(n), 배열 공간 O(n)이다. n=1에서는 1, n=2에서는 3이 나와야 한다.

나머지를 중간 단계에 적용해도 답이 보존된다. (a+2b) mod 10007은 ((a mod 10007)+2(b mod 10007)) mod 10007과 같다. 따라서 dp 배열에 나머지만 저장해도 되고, 계산 중 가장 큰 값도 10006+2×10006으로 int 범위 안이다. 정확한 수를 끝까지 저장하면 int 오버플로가 나므로 마지막에 한 번만 나누는 방식은 틀린다. 답 하나만 필요하다면 직전 두 값만 유지해 공간을 O(1)로 줄일 수 있지만, 배열은 점화식의 각 단계와 예제 추적을 보여 주기 쉽다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

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

        int n = Integer.parseInt(in.readLine());
        out.write("" + tileOf2xn2(n));
        out.write("\n");
        out.flush();
        out.close();
        in.close();
    }
    public static int tileOf2xn2(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i-1] + (2*dp[i-2])) % 10007;
        }
        return dp[n];
    }
}