2xN 타일링

문제

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

입력

첫째 줄에 n이 주어진다 ( 1<= n <= 1000)

출력

첫째 줄에 2xn 크기의 직사각형을 채우는 방법의 수를 10007로 나눈 나머지를 출력

점화식

맨 오른쪽을 어떻게 마무리하는지 보면 중복 없이 두 경우로 나뉜다. 세로 2×1 타일 한 장이면 남은 폭이 n-1이므로 dp[n-1]가지다. 가로 1×2 타일을 위아래 한 장씩 놓으면 남은 폭이 n-2이므로 dp[n-2]가지다. 가로 타일 한 장만 놓으면 2×n 직사각형의 반쪽이 비므로 경우의 수에 넣지 않는다.

왜 이 둘이 빠짐없는 분류일까? 맨 오른쪽 아래 칸을 덮는 타일은 세로 타일이거나 가로 타일뿐이다. 세로라면 오른쪽 열 전체가 채워지고, 가로라면 그 위 두 칸도 가로 타일로 채워야 한다. 두 경우는 오른쪽 아래 칸의 타일 방향이 달라 겹치지 않는다. 각각에서 마지막 한 열 또는 두 열을 떼어 내면 더 작은 직사각형의 배치와 일대일로 대응하므로, 단순한 추측이 아니라 점화식의 근거가 된다.

따라서 dp[n]=dp[n-1]+dp[n-2]다. 빈 폭을 채우는 방법 한 가지를 dp[0]=1, 폭 1을 채우는 방법을 dp[1]=1로 두면 폭 2는 1+1=2, 폭 3은 2+1=3이 된다. dp[0]=1은 빈 타일 하나가 있다는 뜻이 아니라 점화식에서 아무것도 더 놓지 않는 완성 상태 한 가지를 나타낸다.

폭 4를 손으로 따라가 보면 점화식의 두 항이 실제 배치 수를 어떻게 나누는지 알 수 있다.

폭 `i`	마지막 세로 한 장으로 끝나는 배치	마지막 가로 두 장으로 끝나는 배치	`dp[i]`
1	—	—	1
2	`dp[1]=1`	`dp[0]=1`	2
3	`dp[2]=2`	`dp[1]=1`	3
4	`dp[3]=3`	`dp[2]=2`	5

폭 4의 다섯 배치는 세로 타일만 네 장, 가로 타일 두 장의 묶음을 왼쪽·가운데·오른쪽에 한 번 두는 세 배치, 가로 묶음을 두 번 두는 한 배치다. 세로 한 장으로 끝나는 세 배치와 가로 두 장으로 끝나는 두 배치가 위 표의 분할과 일치한다.

각 폭을 한 번 계산하므로 시간 O(n), 배열 공간 O(n)이다. 수가 빠르게 커져서 각 단계에서 10007로 나눈다. n=1은 반복문을 거치지 않고 초기값 1을 반환한다.

코드에서는 dp[i-1]과 dp[i-2]가 이미 10007로 나눈 값이어도 된다. (a+b) mod m = ((a mod m)+(b mod m)) mod m이므로 마지막 나머지는 같다. 매 단계 저장값이 10006 이하라 두 값을 더해도 Java int 범위를 넘지 않는다. 반대로 정확한 경우의 수를 끝까지 int로 저장한 뒤 마지막에만 나누면 먼저 오버플로가 일어나 잘못된 값을 얻는다.

배열은 모든 작은 폭의 답을 보여 주기 좋아 학습용으로 명확하다. 실제 계산에서 필요한 값은 직전 두 개뿐이므로 previous2, previous1 두 변수로 갱신하면 공간을 O(1)로 줄일 수 있다. 갱신할 때는 새 값을 계산한 뒤 이전 값들을 한 칸씩 밀어야 이전 dp[i-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("" + tileOf2xn(n));
        out.write("\n");
        out.flush();
        out.close();
        in.close();
    }
    public static int tileOf2xn(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] + dp[i-2]) % 10007;
        }
        return dp[n];
    }
}