관리 메뉴

Joonas' Note

BOJ 14852 - 타일 채우기 3 본문

알고리즘/문제 풀이

BOJ 14852 - 타일 채우기 3

joonas 2019. 3. 21. 22:51

    링크: 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)\)로 깔끔하게 정리된다.

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

    코드

    비슷한 문제

     

    반응형

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

    BOJ 17142 - 연구소 3  (0) 2019.04.15
    BOJ 17140 - 이차원 배열과 연산  (0) 2019.04.15
    BOJ 14852 - 타일 채우기 3  (0) 2019.03.21
    BOJ 9375 - 패션왕 신해빈  (0) 2019.03.21
    프로그래머스 - 나머지 한 점  (0) 2019.03.16
    BOJ 1405 - 미친 로봇  (0) 2019.03.14
    0 Comments
    댓글쓰기 폼