Joonas' Note

BOJ 14852 - 타일 채우기 3 본문

알고리즘/문제 풀이

BOJ 14852 - 타일 채우기 3

joonas 2019.03.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
댓글쓰기 폼