[백준] BOJ_2133 - 타일 채우기

이종찬·2026년 1월 28일

1. 문제 정보

문제 요약: $3 \times N$ 크기의 벽을 $2 \times 1$ , $1 \times 2$ 크기의 타일로 빈틈없이 채우는 경우의 수를 구하시오.
난이도: Gold 4
제약 조건: $1 \le N \le 30$
링크: 백준 2133번 - 타일 채우기

2. 접근 방식

타일링 문제는 DP(Dynamic Programming)의 대표적인 유형입니다. 하지만 이 문제는 $2 \times N$ 타일링과 다르게 '특이한 모양(Unique Shapes)'이 발생한다는 점에서 난이도가 급상승합니다.

2-1. 문제의 본질

가장 먼저 타일의 넓이를 생각해야 합니다. 우리가 사용하는 타일의 넓이는 $2$ ( $2 \times 1$ )입니다.

벽의 전체 넓이는 $3 \times N$ 입니다.

$N$ 이 홀수라면? 전체 넓이는 $3 \times \text{홀수} = \text{홀수}$ 가 됩니다.
넓이가 2인 타일로 홀수 넓이를 채우는 것은 불가능합니다.
따라서, $N$ 이 홀수일 경우 답은 무조건 0입니다. 우리는 $N$ 이 짝수인 경우만 고려하면 됩니다.

2-2. 알고리즘 설계

$N$ 이 커질 때 경우의 수가 어떻게 늘어나는지 단계별로 분석해 봅시다.

$N=2$ 인 경우 ( $DP[2]$ )
- $3 \times 2$ 벽을 채우는 기본 방법은 3가지입니다. (가로 3개, 세로+가로 조합 등)
- $\therefore DP[2] = 3$
$N$ 을 확장할 때 일반적인 경우 ( $3 \times DP[N-2]$ )
- $N$ 칸을 채울 때, 가장 오른쪽 $2$ 칸을 $N=2$ 의 경우(3가지 패턴)로 채우고, 나머지 $N-2$ 칸을 채우는 경우입니다.
- 즉, $DP[N-2] \times 3$ 이 기본 베이스가 됩니다.
예외 케이스: 특이한 모양 ( $Unique\ Shapes$ )
- 여기서 많은 분들이 실수합니다. 단순히 $DP[N] = DP[N-2] \times 3$ 으로 끝내면 오답입니다.
- $N=4$ 일 때, $2$ 칸씩 쪼개지지 않는 고유한 패턴 2개가 새로 생깁니다.
- $N=6, 8, 10, \dots$ 짝수 $N$ 이 늘어날 때마다, 해당 길이에서만 만들 수 있는(중간에 세로선으로 쪼개지지 않는) 고유 패턴이 항상 2개씩 존재합니다.

2-3. 최종 점화식

위의 논리를 종합하면, $DP[N]$ 을 구하기 위해서는 $N-2$ 의 결과뿐만 아니라 $N-4, N-6, \dots, 0$ 까지의 모든 결과를 참조해야 합니다.

$DP[N] = (DP[N-2] \times 3) + \sum_{k=4, 6, \dots}^{N} (DP[N-k] \times 2)$

이 수식을 코드로 옮길 때, $DP[0] = 1$ 로 초기화해두면(아무것도 안 놓는 경우 1가지), 수식을 깔끔하게 처리할 수 있습니다.

3. 코드 구현

3-1. 실패한 코드 (논리 오류)

단순히 $DP[N]$ 을 구할 때 앞뒤의 곱으로만 처리하려 했으나, 이는 중복 집계와 누락이 동시에 발생하는 잘못된 접근입니다. 타일링에서 '분할 정복'처럼 접근할 때는 겹치는 경계선을 매우 주의해야 합니다.

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());

        if (N % 2 == 1) {
            System.out.println(0);
            return;
        }

        dp = new int[N + 1];
        dp[2] = 3;
        // 논리적 오류: 단순히 양쪽 끝을 기준으로 곱하는 방식은 
        // 3xN 타일링의 '고유 패턴(Unique Shapes)'을 정확히 반영하지 못합니다.
        for (int n = 4; n <= N; n += 2) {
            int i = n - 2;
            int j = 2;

            while (i >= j) {
                dp[n] += (dp[i] * dp[j]);
                i -= 2;
                j += 2;
            }
            dp[n] += 2;
        }

        System.out.println(dp[N]);
    }
}

3-2. 정답 코드 (O(N^2))

위에서 유도한 점화식을 그대로 구현한 코드입니다. 이중 반복문을 사용하여 이전의 모든 짝수 $DP$ 값을 참조합니다.

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());

        // 홀수인 경우 0 출력
        if (N % 2 == 1) {
            System.out.println(0);
            return;
        }

        dp = new int[N + 1];
        dp[0] = 1; // 특이 케이스 계산을 위한 초기값
        dp[2] = 3;

        for (int n = 4; n <= N; n += 2) {
            // 1. N-2까지 채우고 2칸을 채우는 경우 (3가지)
            dp[n] = dp[n - 2] * dp[2]; 
            
            // 2. 특이 케이스 누적 (4칸 이상 떨어진 곳들의 경우의 수 * 2)
            for (int i = 4; i <= n; i += 2) {
                dp[n] += dp[n - i] * 2;
            }
        }

        System.out.println(dp[N]);
    }
}

3-3. 최적화 코드 (O(N))

내부 반복문이 계속해서 sum을 구하는 구조임을 파악하면, 이를 변수 하나로 관리하여 $O(N)$ 으로 최적화할 수 있습니다.

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static long[] dp; // N이 30이면 int 범위를 넘을 수 있으므로 long 권장 (문제 범위상 int도 가능은 함)

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());

        if (N % 2 == 1) {
            System.out.println(0);
            return;
        }

        dp = new long[N + 1];
        dp[0] = 1;
        dp[2] = 3;
        
        long sum = 0; // 이전까지의 특이 케이스 누적합 (dp[N-4]*2 + dp[N-6]*2 ...)

        for (int n = 4; n <= N; n += 2) {
            // 직전 단계의 특이 케이스 값을 sum에 추가
            sum += dp[n - 4] * 2;

            // 점화식: (바로 앞 단계 * 3) + (지금까지 누적된 특이 케이스들의 합)
            dp[n] = (dp[n - 2] * 3) + sum;
        }

        System.out.println(dp[N]);
    }
}

4. 회고 및 배운 점

4-1. 시간 복잡도 분석

기본 DP ( $O(N^2)$ ): $N$ 번째 값을 구하기 위해 $0$ 부터 $N-2$ 까지 짝수 인덱스를 다시 순회해야 합니다. $N \le 30$ 이라 문제없지만, $N$ 이 커지면 비효율적입니다.
최적화 DP ( $O(N)$ ): sum 변수를 활용해 반복되는 덧셈 연산(Memoization of Sum)을 수행했습니다. 이를 통해 내부 반복문을 제거했습니다.