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)\)을 출력한다.

코드

타일 시리즈

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

 

반응형

• 카카오스토리
• 트위터
• 페이스북

'알고리즘 > 문제 풀이' 카테고리의 다른 글

BOJ 5612 - 터널의 입구와 출구  (0)	2019.11.06
BOJ 13325 - 이진 트리  (0)	2019.09.16
BOJ 17142 - 연구소 3  (0)	2019.04.15
BOJ 17140 - 이차원 배열과 연산  (0)	2019.04.15
BOJ 14852 - 타일 채우기 3  (0)	2019.03.21