BOJ 14852 - 타일 채우기 3
Joonas' Note
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×g(n−1)+f(n−2)로 깔끔하게 정리된다.
이를 코드로 옮기면 생각보다 단순하다.
코드
코드보기
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstdio> | |
const int MOD = 1e9 + 7; | |
int f[1000001]; | |
int g[1000001]; | |
int main() { | |
int n; | |
scanf("%d", &n); | |
// f(n) = f(n-2)+2*g(n) | |
// g(n) = f(n-1)+f(n-2)+g(n-2) | |
f[0] = 1; f[1] = 2; | |
g[0] = 0; g[1] = 1; | |
for (int i = 2; i <= n; ++i) { | |
g[i] = ((f[i - 1] + f[i - 2]) % MOD + g[i - 2]) % MOD; | |
f[i] = (f[i - 2] + (2 * g[i]) % MOD) % MOD; | |
} | |
printf("%d\n", f[n]); | |
return 0; | |
} |
비슷한 문제
- BOJ 2133번 - 타일 채우기 (3×N 크기의 벽) [풀이]
- BOJ 2718번 - 타일 채우기 (4×N 크기의 벽) [풀이]
- BOJ 13976번 - 타일 채우기 2 (3×N 크기의 벽) [풀이]
- BOJ 14852번 - 타일 채우기 3 (2×N 크기의 벽) [풀이]
- BOJ 15700번 - 타일 채우기 4 (N×M 크기의 벽)
'알고리즘 > 문제 풀이' 카테고리의 다른 글
BOJ 17142 - 연구소 3 (0) | 2019.04.15 |
---|---|
BOJ 17140 - 이차원 배열과 연산 (0) | 2019.04.15 |
BOJ 9375 - 패션왕 신해빈 (0) | 2019.03.21 |
프로그래머스 - 나머지 한 점 (0) | 2019.03.16 |
BOJ 1405 - 미친 로봇 (0) | 2019.03.14 |