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

문제

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

풀이

dp로 풀이할 수 있는 문제
$f(1) = 1, f(2) = 2$ 이다. 이는 그림을 그리면 쉽게 확인할 수 있다.

f(3)을 구해야하는데, 이는 $f(1)$에다가 2x2의 타일을 하나 붙이기 + $f(2)$ 에다가 2x1 타일을 하나 붙인 것과 동일하다.

2x2 타일은 || 이렇게 생긴 타일은 붙일 수가 없다.
f(3)을 예시로 들면 f(1)이 | 이라고 가정하고, 2x2인 || 타일을 붙인다고 가정할 때, f(2)인 || 타일에 |을 붙이는 것과 동일하기 때문이다.
따라서 2x2 타일은 = 와 같인 타일밖에 붙일 수 없다.

점화식은 다음과 같다.
$f(1) = 1, f(2) = 2$
$f(n) = f(n - 1) + f(n - 2)$

소스코드

후기

중복되는 타일이 있어서 조금 헷갈릴 수 있었던 문제