[DP] boj 2133 - 복잡한 점화식

백준 2133은 점화식을 완전히 이해하는 데 시간이 걸렸다. 가장 도움 된 참고 링크

점화식 설명

n일 때의 결과를 f(n)이라고 쓰면

1. n은 짝수 : 3xn을 1x2와 2x1로 채우려면 n은 반드시 짝수여야 된다.

2. f(n-2) * f(2)는 기본으로 깔고 간다 : f(n)을 f(n-2)의 우측에 빈 바닥 3x2가 생겼다고 보는 관점.

3. 특이 케이스를 왼쪽만 계산했기 때문에 우측도 세야 된다 : 빈 바닥이 우측이 아니고 좌측에 생겼다면 이 때 2번과 다른 경우가 없는지 확인이 필요하다. 대부분의 경우는 중복이겠지만, 특이케이스와 연관된 경우는 그림이 다르니 더해줘야 된다.

n = 8일 때를 예로 들자면,

f(8-6) * (n = 6일 때의 특이케이스 2가지) + f(8-4) * (n = 4일 때의 특이 케이스 2가지)

곧 f(2) * 2 + f(4) * 2를 더해줘야 되는 셈이다. 다른 사람들의 점화식에서 갑자기 나타난 2*3의 정체가 여기서의 f(2) * 2 부분이다. 참고 링크

4. 매번 특이케이스가 2개씩 생긴다 : 특이케이스는 n = 6까지 직접 그려봤다. 힌트로 준 그림에서 n = 4일 때 특이케이스를 볼 수 있는데, 이의 확장판이다. 참고 링크

 

3번에서 2*3만 따로 더하는 게 싫어서 이렇게 짰다.

import sys

def calcNumberOfCases(num, __cache = {0:1, 2:3}):
    if num % 2 == 1:
        return 0
    if num in __cache:
        return __cache[num]

    tempSum = 0
    for i in range(4, num-1, 2):
        tempSum += 2 * calcNumberOfCases(num-i)
    __cache[num] = __cache[2] * calcNumberOfCases(num-2) + tempSum + 2

    return __cache[num]

n = int(sys.stdin.readline())
print(calcNumberOfCases(n))