관리 메뉴

Joonas' Note

UVa 10918 - Tri Tiling 본문

알고리즘/문제 풀이

UVa 10918 - Tri Tiling

joonas 2019. 4. 15. 15:55

    링크 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 5612 - 터널의 입구와 출구  (0) 2019.11.06
    BOJ 13325 - 이진 트리  (0) 2019.09.16
    UVa 10918 - Tri Tiling  (3) 2019.04.15
    BOJ 17142 - 연구소 3  (0) 2019.04.15
    BOJ 17140 - 이차원 배열과 연산  (0) 2019.04.15
    BOJ 14852 - 타일 채우기 3  (0) 2019.03.21
    3 Comments
    댓글쓰기 폼