백준 2133 타일 채우기 문제는 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제는 동적 계획법(DP, Dynamic Programming)을 사용하여 해결할 수 있습니다.
이 문제를 해결하기 위해 f(n)을 3×n 크기의 벽을 2×1, 1×2 타일로 채우는 방법의 수라고 정의합니다.
기본적인 아이디어는 다음과 같습니다:
- 기저 사례:
- f(0) = 1: 빈 벽(3×0)에는 타일을 채우는 방법이 1가지입니다 (아무것도 하지 않는 것).
- f(1) = 0: 3×1 크기의 벽은 2×1 또는 1×2 타일로 채울 수 없으므로 경우의 수는 0입니다.
- f(2) 경우의 수:
- 두 개의 1×2 타일을 수직으로 놓는 방법
- 세 개의 2×1 타일을 가로로 놓는 방법
- f(3) = 0: 3×3 크기의 벽은 2×1 또는 1×2 타일로 채울 수 없으므로 경우의 수는 0입니다.
- f(4) 경우의 수:
- 2×1 타일을 이용하여 모든 칸을 채우는 방법 (기본 패턴): 3가지 패턴
- 중간에 2×2 타일을 이용하여 채우는 방법 (가로, 세로로 두 번씩 사용할 수 있음): 2가지 패턴
- 전체 타일을 2×1, 1×2 타일을 혼합하여 채우는 방법: 2가지 패턴
- f(5) = 0: 3×5 크기의 벽은 2×1 또는 1×2 타일로 채울 수 없으므로 경우의 수는 0입니다.
- f(6) 경우의 수:
- 2×1 타일을 이용하여 모든 칸을 채우는 방법 (기본 패턴): 3가지 패턴
- 중간에 2×2 타일을 이용하여 채우는 방법 (가로, 세로로 두 번씩 사용할 수 있음): 2가지 패턴
- 전체 타일을 2×1, 1×2 타일을 혼합하여 채우는 방법: 4가지 패턴
- f(0) =1, f(2) = 3, f(4) = 11, f(6) = 41
- 점화식:
- f(n) = 4*f(n-2) - f(n-4): 여기서 f(n-2)는 두 칸을 차지하는 기본적인 타일 배치이고, 4는 여러 타일을 배치하는 방법에서 유도된 상수입니다. f(n-4)는 겹치는 타일 배치를 제거하는 데 사용됩니다.
점화식의 유도:
- f(n)을 구하기 위해선 이전의 경우들을 이용하여 모든 가능한 타일 배치를 고려해야 합니다. f(n-2)는 f(n)에서 두 칸을 채울 수 있는 가장 기본적인 배치입니다. 이 때 3가지 추가 타일 배치의 가능성을 고려해야 하므로 4*f(n-2)가 됩니다.
- 그러나 일부 타일 배치가 중복될 수 있으므로, 이를 제거하기 위해 f(n-4)를 빼줍니다.
import java.util.Scanner;
/**
* 제목 : 타일 채우기
* 링크 : https://www.acmicpc.net/problem/2133
* 분류 : Dynamic Programming
*/
public class Main {
static long[] dp = new long[31];
static {
dp[0] = 1;
dp[1] = 0;
dp[2] = 3;
dp[3] = 0;
dp[4] = 11;
dp[5] = 0;
dp[6] = 41;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i = 6; i <= n; i += 2) dp[i] = 4 * dp[i - 2] - dp[i - 4];
System.out.println(dp[n]);
}
}