백준 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))
'Algorithm' 카테고리의 다른 글
[그래프] boj 2331 - 반복수열 (0) | 2021.01.04 |
---|---|
[DP] boj 11057 - 오르막 수 (0) | 2021.01.03 |
[DP] boj 11053, 11054, 11055, 11722 - 가장 긴 증가하는 부분 수열(LIS) (0) | 2021.01.01 |
[DP] boj 11726, 11727 - 2xn 타일링 (0) | 2021.01.01 |
[DP] boj 1912 - 연속합 (0) | 2021.01.01 |