BOJ 14852 - 타일 채우기 3

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

문제

타일 시리즈 중 하나인데, 2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구하는 문제이다.

먼저 왼쪽부터 타일을 채워가면서 생기는 모양에 따라 부분 문제를 만들어나간다.
아래와 같은 모양을 각각 $f(n), g(n)$이라고 정의해보자. $g(n)$은 첫 번째 열 중에서 한 칸만 채워진 경우이다.

두 모양이 채워질 수 있는 Base case를 이렇게 정의하자.

$f(0)$은 모든 타일을 채웠다는 뜻으로 1개로 센다. $g(0)$은 불가능한 모양이므로 0이다.

 

먼저 $g(n)$은 아래와 같이 세 가지 모양으로 전개될 수 있다.

첫 번째 열의 빈칸에 1×1짜리 타일을 하나 채우면 $f(n-1)$의 모양이 나온다.
1×2짜리 타일을 하나 채우면 1×1짜리 타일를 붙인 $f(n-2)$의 모양과 1×2짜리 타일붙인 $g(n-2)$의 모양이 가능하다.

 

$f(n)$의 경우에는 $g(n-1)$이 상하반전으로 2개, $f(n-1)$, $f(n-2)$의 모양이 나오지만, 2개의 $g(n-1)$ 모양에서 1×1짜리 타일을 2개 채운 $f(n-1)$의 모양이 1번 중복된다.

식을 정리하면 $f(n)~=~2 \times g(n-1) + f(n-2)$로 깔끔하게 정리된다.

이를 코드로 옮기면 생각보다 단순하다.

코드

	#include <cstdio>
	const int MOD = 1e9 + 7;
	int f[1000001];
	int g[1000001];
	int main() {
	int n;
	scanf("%d", &n);
	// f(n) = f(n-2)+2*g(n)
	// g(n) = f(n-1)+f(n-2)+g(n-2)
	f[0] = 1; f[1] = 2;
	g[0] = 0; g[1] = 1;
	for (int i = 2; i <= n; ++i) {
	g[i] = ((f[i - 1] + f[i - 2]) % MOD + g[i - 2]) % MOD;
	f[i] = (f[i - 2] + (2 * g[i]) % MOD) % MOD;
	}
	printf("%d\n", f[n]);
	return 0;
	}

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

비슷한 문제

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