UVa 10918 - Tri Tiling

링크 1: https://uva.onlinejudge.org/...problem=1859
링크 2: BOJ 2133 - 타일채우기(https://www.acmicpc.net/problem/2133)

문제

타일 시리즈 중에 하나로, 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 문제이다.

풀이

3×n 크기의 벽을 채우는 경우의 수를 $f(n)$이라고 하자. 다음은 전개될 수 있는 모든 모양이다. 모양이 반복되는 경우까지만 적었다.

       ....         x...    ....
f(n) = ....  g(n) = .... or ....
       ....         ....    x...

A.....    AA.... 
A..... or ...... 
......    ...... 

A.....    ACC...    ACC...    ACC... 
A..... -> A..... -> ADD... -> ADD... 
BB....    BB....    BB....    BBEE.. 
g(n-1)                        g(n-3)

A.....    AC.... 
A..... -> AC.... 
BB....    BB....
g(n-1)    f(n-2) 

AA....    AA.... 
BB.... -> BB.... 
......    CC....
          f(n-2) 

AA....    AA.... 
B..... -> BC.... 
B.....    BC....
g(n-1)    f(n-2)  

AA....    AA....    AA....     AAEE.. 
B..... -> BCC... -> BCC...  -> BCC... 
B.....    B.....    BDD...     BDD... 
g(n-1)                         g(n-3)

그림으로 나타내면 이렇다.

정리하자면, $f(0) = 1,~ f(1) = 0,~ g(0) = 0,~ g(1) = 1$ 이고
$\begin{cases} f(n) = f(n-2) + 2 \cdot g(n-1) \\ g(n) = f(n-1) + g(n-2) \end{cases}$

위 식을 한번 더 정리하면, $f(n) = 4 \cdot f(n-1) - f(n-2)$가 나온다!

문제에서는 입력 $n$에 대해 $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;
	while (~scanf("%d", &n) && n >= 0) printf("%d\n", f[n]);
	return 0;
	}

view raw uva-10918.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 크기의 벽)