BOJ 14852 - 타일 채우기 3

Joonas' Note

BOJ 14852 - 타일 채우기 3 본문

알고리즘/문제 풀이

BOJ 14852 - 타일 채우기 3

2019. 3. 21. 22:51 joonas 읽는데 4분
  • 문제
  • 코드
  • 비슷한 문제

링크: 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(n1)의 모양이 나온다.
1×2짜리 타일을 하나 채우면 1×1짜리 타일를 붙인 f(n2)의 모양과 1×2짜리 타일붙인 g(n2)의 모양이 가능하다.

 

f(n)의 경우에는 g(n1)이 상하반전으로 2개, f(n1), f(n2)의 모양이 나오지만, 2개의 g(n1) 모양에서 1×1짜리 타일을 2개 채운 f(n1)의 모양이 1번 중복된다.

식을 정리하면 f(n) = 2×g(n1)+f(n2)로 깔끔하게 정리된다.

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

코드

코드보기
#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;
}
view raw boj-14852.cpp hosted with ❤ by GitHub

비슷한 문제

 

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

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
Comments