greentea31's Note

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

풀이 과정

https://greentea31.tistory.com/26

위와 비슷하게 DP로 풀기 위해 점화식을 세워서 문제를 해결할 수 있다.

문제를 보고 생각을 하다보면 3x2 블록을 채우는 경우의 수는 3개가 있으니 3x4는 3x2 블록 2개 붙이면 되겠고... 이런 생각이 들겠지만 밑에 힌트를 보면 3x2 블록 채우는 경우의 수를 2개 조합한게 아닌 3x4 블록을 채우는 방법이 존재함을 알게 된다.

3xi 에서 i가 2씩 늘어날 수록 기존의 방법의 조합이 아닌 새로운 방법이 2개씩 더 추가된다.

따라서 d[i]를 3xi 블록을 채우는 방법의 경우의 수라고 하면

d[i] = 3 * d[i-2] + 2 * d[i-4] + 2 * d[i-6] + ... + 2 * d[0]이 성립한다.

d[0]은 1로 초기값을 설정해놔야 정답을 얻을 수 있다.

소스 코드

import sys

N = int(sys.stdin.readline())
d = [1, 0, 3, 0, 11]
for i in range(5, 31):
    d.append(3*d[i-2])
    for j in range(4, i+1, 2):
        d[i] += 2*d[i-j]

print(d[N])