BOJ 2133 - 타일 채우기

링크: https://www.acmicpc.net/problem/2133

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제이다.

 

풀이

3×N 벽을 채우는 경우를 $f(n)$, 한 칸이 빈 3×N 벽을 채우는 경우를 $g(n)$ 라고 하자.

왼쪽부터 2×1 또는 1×2 크기의 타일을 하나씩 채워보면서 가능한 경우를 살펴본다.

f(n)이 가능한 경우의 수

g(n)이 가능한 경우의 수

$g(0)$와 $g(2)$는 타일을 채울 방법이 없으므로 $g(0) = g(2) = 0$ 이다.

---

이것을 식으로 나타내면 이렇다.

$$f(n) = \begin{cases} 0 & \text{if $n$ < 2} \\ 2g(n-1) + f(n-2) \end{cases}$$

$$g(n) = \begin{cases} 1 & \text{if $n$ = 1} \\ 0 & \text{if $n$ < 3} \\ g(n-2) + f(n-1) \end{cases}$$

이대로 코드를 구현해서 $f(n)$을 구하면 정답이다.

 

	#include <cstdio>
	int main() {
	int f[32], g[32];
	f[0] = g[1] = 1;
	f[1] = g[0] = 0;
	for (int n = 2; n <= 30; ++n) {
	f[n] = 2 * g[n - 1] + f[n - 2];
	g[n] = f[n - 1] + g[n - 2];
	}
	int n;
	scanf("%d", &n);
	printf("%d\n", f[n]);
	return 0;
	}

view raw boj-2133.cpp hosted with ❤ by GitHub

 

---

풀이 2

두 함수가 상호 참조하는(꼬여있는) 형태가 아니라 하나의 점화식으로 합칠 수 있다.
$N$이 홀수일 때는 답이 항상 나올 수 없으므로, 짝수에 대해서 점화식을 하나로 합쳐보자.

먼저 $g(n)$에 대해서 점화식을 한 쪽으로 정리한다.
여기서 $n$은 $f(n)$에서 $g(n-1)$을 계산하므로 $g(n)$을 전개할 때는 홀수로 가정해야한다.

$$\begin{align} g(n) & = g(n-2) + f(n-1) \\ & = g(n-2) + \{ 2g(n-2) + f(n-3) \} \\ &= g(n-2) + 2 \cdot  (g(n-2) + g(n-4) + g(n-6) + \cdots + g(1) ) + f(0) \\ &= g(n-2) + 2 \cdot  (g(n-2) + g(n-4) + g(n-6) + \cdots + 1 ) + 0 \end{align}$$

 

$f(0) = 0$ 이라서 식에 $g(n)$ 꼴만 남는다. $g(n)$과 $g(n-2)$를 전개해서 둘을 상쇄시킬 것이다.

$$\begin{align} g(n) & = g(n-2) + 2 \cdot (g(n-2) + g(n-4) + \cdots + g(1)) \\ g(n-2) & = g(n-4) + 2 \cdot (g(n-4) + g(n-6) + \cdots + g(1)) \end{align}$$

 

이제 $g(n) - g(n-2)$를 구해보면 식이 정리된다.

$$\begin{align} g(n) - g(n-2) & = g(n-2) - g(n-4) + 2 \cdot g(n-2) \\ \therefore ~ g(n) & = 4 \cdot g(n-2) - g(n-4) \end{align}$$

이렇게하면 $g(n)$에 대한 점화식을 구할 수 있다.

---

그런데 여기서 굳이 $f(n)$을 다시 계산할 필요가 없다.

왜냐하면, $g(n)$은 한 칸이 없는 3×N 크기의 벽을 채우는 것인데,
여기서 그냥 2칸이 더 없다고 생각하면 (또는 타일 하나를 그냥 미리 두었다고 생각하면), $f(n-1)$과 같은 모양이기 때문이다.

즉, $g(n+1)$ 만 구해서 출력하면 그것이 정답이 된다.

코드

	#include <cstdio>
	int main() {
	int n;
	scanf("%d", &n);
	int g[32] = {};
	g[1] = 1; g[3] = 3;
	for (int i = 5; i <= n + 1; ++i) {
	g[i] = 4 * g[i - 2] - g[i - 4];
	}
	printf("%d\n", g[n+1]);
	return 0;
	}

view raw boj-2133-2.cpp hosted with ❤ by GitHub

 

코드에서 g[n]의 값은 여태 설명한 그림(한 칸이 없는 3×N 크기의 벽)과는 다르다.
결과적으로 $f(n)$을 저장하기 때문에, 초기 값으로 $g(3) = 3$ 이 들어간다.

참고로 이 문제로 만들어지는 수열은 OEIS A001835 수열과 같다.

다른 문제

• BOJ 2133번 - 타일 채우기 (3×N 크기의 벽) [풀이]
• BOJ 2718번 - 타일 채우기 (4×N 크기의 벽) [풀이]
• BOJ 13976번 - 타일 채우기 2 (3×N 크기의 벽) [풀이]
• BOJ 14852번 - 타일 채우기 3 (2×N 크기의 벽) [풀이]
• BOJ 15700번 - 타일 채우기 4 (N×M 크기의 벽)