[BOJ] 백준 11727 2xn 타일링 2 (Swift)

문제

https://www.acmicpc.net/problem/11727

풀이

dp로 풀 수 있는 문제

2x1 을 놓을 수 있는 경우의 수 = 1
2x2 을 놓을 수 있는 경우의 수 = 3 이지만, || 블럭을 제외하면 2개이다.

2x3을 놓을 수 있는 경우의 수는 5이고, 직접 그려서 세보았다.
이것을 어떻게 도출해 낼 수 있을지 한 번 생각해보자.

2x1 까지 채워져 있는 경우, 해당 경우에서 '=' 블럭과, 2x2 블럭을 넣는 두가지 경우가 있다.
2x2 까지 채워져 있는 경우에는 | 블럭밖에 놓을 수 없다.

여기서 점화식을 도출 할 수 있다.
$f(1) = 1, f(2) = 3$
$f(n) = f(n-1) + 2*f(n-2)$

소스코드

후기

기본적인 dp 문제였다.