[BOJ 2718] 타일 채우기

문제

---

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

풀이

---

그냥 수학 문제 풀듯 풀었다.

f(n)을 4 x n 타일을 채우는 경우의 수라고 하고, g(n)을 (0, 0), (1, 0)이 제거된 4 x n 타일을 채우는 경우의 수, h(n)을 (0, 0), (3, 0)이 제거된 4 x n 타일을 채우는 경우의 수라고 하자 (좌상단이 (0, 0)이고 우하단이 (3, n - 1)이다.)

그리고 4 x N 타일의 첫 행을 채우는 방식은 5가지가 있다.

그러면 다음과 같은 점화식들이 성립한다.

f(n) = f(n - 1) + f(n - 2) + 2 * g(n - 1) + h(n - 1)

g(n) = f(n - 1) + g(n - 1)

h(n) = f(n - 1) + h(n - 2)

이유는 생략한다.

initial value에 유의해서 코드를 짜주면 된다.

코드

---

import sys

dp0 = [1, 1, 5]
dp1 = [1]
dp2 = [1]
i = 2

for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    for j in range(i + 1, n + 1):
        if j % 2:
            dp0.append(dp0[-1] + dp0[-2] * 4 + dp1[-1] * 3 - dp2[-1])
        else:
            dp0.append(dp0[-1] + dp0[-2] * 4 + dp1[-1] * 2 + dp2[-1])
            dp2.append(dp2[-1] + dp0[-3])
        dp1.append(dp1[-1] + dp0[-3])

    i = n
    print(dp0[n])