문제 출처 : https://www.acmicpc.net/problem/9184

문제 파악

주어진 수도코드 w(a,b,c) 를 파이썬 코드로 구현해하는 문제이다.

그러나 그냥 수도코드 그대로 그저 완전탐색인 방법으로 파이썬 코드로 옮기게 되면
시간복잡도가 O(3^{x+y+z}) 이므로 3^60 = 9^30 이다
python은 보통 10⁷ 정도까지 시간초과가 나지 않으므로 9^30으로는 재귀로 풀지 못한다.

재귀호출로 푼 코드

import sys
input = sys.stdin.readline


def w(x,y,z):
    if x <= 0 or y <= 0 or z <= 0:
        return 1

    if x > 20 or y > 20 or z >20:
        return w(20,20,20)
    
    if x < y and x < z:
        return w(x, y, z-1) + w(x, y-1, z-1) - w(x, y-1, z)
    else:
        return w(x-1, y, z) + w(x-1, y-1, z) + w(x-1, y, z-1) - w(x-1, y-1, z-1)

while True:
    a, b, c = map(int,input().split())

    # -1 -1 -1 나올때 탈출
    if a == b == c == -1:
        exit()

    print(w(a,b,c))    

이 문제는 w(x,y,z)를 여러 조건으로 쪼개 재귀 호출한다.
동일한 (x,y,z)가 기하급수적으로 중복 호출되기 때문에
값을 기억해놓고 재활용하는 '메모이제이션' 기법을 써야 한다.

해답 및 풀이

import sys
input = sys.stdin.readline

memoization = []
for i in range(21):
    row = []
    for j in range(21):
        row2 = []
        for k in range(21):
            row2.append(None)
        row.append(row2)
    memoization.append(row)


def w(x,y,z):
    if x <= 0 or y <= 0 or z <= 0:
        return 1

    if x > 20 or y > 20 or z >20:
        return w(20,20,20)
    
    # 여기에 메모이제이션 로직 추가
    # 계산 전 memoization[a][b][c]가 이미 채워져 있으면 즉시 반환
    if memoization[x][y][z] is not None:
    # if memoization[x][y][z]: 이렇게 써도 됨
        return memoization[x][y][z]
    
    # 위에 안걸렸다는 것은, 메모된 값 없다는 뜻. 여기서 메모이제이션 해줌
    # 없으면 계산 후 저장하고 반환
    if x < y and x < z:
        memoization[x][y][z] = w(x, y, z-1) + w(x, y-1, z-1) - w(x, y-1, z)
    else:
        memoization[x][y][z] = (w(x-1, y, z) + w(x-1, y-1, z) + w(x-1, y, z-1) - w(x-1, y-1, z-1))
    
    return memoization[x][y][z]

while True:
    a, b, c = map(int,input().split())

    # -1 -1 -1 나올때 탈출
    if a == b == c == -1:
        exit()

    print(f'w({a}, {b}, {c}) = {w(a,b,c)}')

메모이제이션 해놓은 값이 있다면 -> 그 값을 반환
메모이제이션 해놓은 값이 없다면 -> 메모이제이션 하고, 반환

이것이 메모이제이션의 핵심인 듯 하다.