사각형 채우기 3

문제 개요

2 × N 크기의 사각형을 1×2, 2×1, 1×1 타일로 채우는 방법의 수를 구하는 문제다. 단, 경우의 수는 1,000,000,007로 나눈 나머지를 출력한다.

예를 들어 N=2일 때는 아래 7가지 방법으로 채울 수 있다:

• 1×2, 1×2
• 2×1, 2×1
• 1×1 네 개
• 2×1 + 1×1 두 개
• 1×2 + 1×1 두 개
• 2×1 + 1×2
• 1×2 + 2×1

---

해결 전략

접근 방법

동적 계획법(DP)을 사용하여 점화식을 세운다. dp[i]는 2×i 크기의 직사각형을 채우는 방법의 수를 의미한다.

타일을 채우는 마지막 방법에 따라 세 가지 주요 경우로 나눈다:

1. 한 열만 남은 경우 (i-1까지 채운 상태):
   가능한 방식 2가지 → 2 × dp[i-1]

2. 두 열만 남은 경우 (i-2까지 채운 상태):
   가능한 방식 3가지 → 3 × dp[i-2]

3. 세 열 이상 남은 경우 (i-k까지 채운 상태, 3 ≤ k ≤ i):
   가능한 방식은 각 k에 대해 2가지 → 2 × (dp[i-3] + dp[i-4] + ... + dp[0])

이 구조는 단순히 이전 값을 기반으로 확장하는 것이 아니라, 마지막에 전혀 다른 형태의 독립적인 블럭 구조가 붙는다는 점에서 일반적인 피보나치 점화식과 다르다.

---

왜 dp[i-3] 이하까지 고려해야 하는가

단순한 2×N 타일 문제에서는 dp[i] = dp[i-1] + dp[i-2]로 충분하다. 하지만 이 문제는 1×1 타일이 추가되면서 다양한 블럭 조합이 가능해졌고, 그 중 일부는 오직 i-3 이하까지 채운 후 마지막 k칸에서만 가능한 독립적인 블럭 구성이다.

예를 들어 2×4를 생각해보면, 아래와 같은 구조는 오직 4칸 전체를 한 번에 채울 때만 등장한다:

이런 구조는 이전 상태(dp[3] 등)에서 한 칸씩 추가해선 만들 수 없다.
그건 이전 길이의 확장이 아닌 고정된 새로운 구성 방식이며, 점화식에서 2 × dp[i-k] 꼴로 처리된다.

---

점화식

초기값:

dp[0] = 1
dp[1] = 2

점화식:

dp[i] = 2 × dp[i-1] + 3 × dp[i-2] + 2 × (dp[i-3] + dp[i-4] + ... + dp[0])

---

구현 코드 (Java)

import java.util.Scanner;

public class Main {
    public static final int MOD = 1000000007;
    public static final int MAX_N = 1000;

    public static int n;
    public static long[] dp = new long[MAX_N + 1];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        dp[0] = 1;
        dp[1] = 2;

        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] * 2 + dp[i - 2] * 3) % MOD;
            for (int j = i - 3; j >= 0; j--)
                dp[i] = (dp[i] + dp[j] * 2) % MOD;
        }

        System.out.print(dp[n]);
    }
}

---

요약

이 문제는 단순한 확장 방식의 점화식으로 해결되지 않는다. 1×1 타일의 존재로 인해 특정 길이에서만 등장하는 독립적인 타일 구성들이 있기 때문이다. 따라서 dp[i]를 계산할 때는 i-3 이하의 상태도 반드시 고려해야 전체 경우의 수를 누락 없이 셀 수 있다.