BOJ 14852 - 타일 채우기 3

링크: 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 2133번 - 타일 채우기 (3×N 크기의 벽) [풀이]
• BOJ 2718번 - 타일 채우기 (4×N 크기의 벽) [풀이]
• BOJ 13976번 - 타일 채우기 2 (3×N 크기의 벽) [풀이]
• BOJ 14852번 - 타일 채우기 3 (2×N 크기의 벽) [풀이]
• BOJ 15700번 - 타일 채우기 4 (N×M 크기의 벽)