[백준/Java] 2133 - 타일 채우기

승래·2026년 3월 13일

DP 백준 자바

백준 2133 - 타일 채우기

요구사항

3 x N 크기의 벽을 2 x 1 타일로 채우는 경우의 수를 구하는 문제
N이 홀수면 채울 수 없으므로 0 출력

접근 방식

DP 로 풀었다.

핵심 관찰

N이 홀수면 3 x N은 항상 홀수 칸 → 2 x 1 타일로 채울 수 없음 → 0
N이 짝수일 때만 경우의 수 존재

경우의 수 분석

N=2일 때: 3가지

→ dp[2] = 3

N=4일 때: 11가지

dp[2] * 3 = 9가지 (N=2 경우에 N=2 이어붙이기)
N=4에서만 나오는 특수한 2가지 추가
→ dp[4] = 9 + 2 = 11

N=6일 때: 41가지

dp[4] * 3 = 33가지
N=4 특수 2가지에 N=2 이어붙이기: dp[2] * 2 = 6가지
N=6에서만 나오는 특수한 2가지 추가
→ dp[6] = 33 + 6 + 2 = 41

점화식

dp[n] = dp[n-2] * 3 + 2
        + dp[n-4] * 2
        + dp[n-6] * 2
        + ...
        + dp[2] * 2

→ 짝수 N마다 항상 새로운 특수 2가지가 추가되므로
   이전 모든 짝수 항의 * 2 누적합이 필요하다

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());

        if (n % 2 != 0) {
            System.out.println(0);
            return;
        }

        if (n == 2) { System.out.println(3); return; }
        if (n == 4) { System.out.println(11); return; }

        int[] dp = new int[n + 1];
        dp[2] = 3;
        dp[4] = 11;

        for (int i = 6; i <= n; i += 2) {
            dp[i] = dp[i-2] * 3 + 2;
            for (int j = i-4; j >= 2; j -= 2) {
                dp[i] += dp[j] * 2;
            }
        }
        System.out.println(dp[n]);
    }
}