🥈 9184번: 신나는 함수 실행

👉🏻 9184번: 신나는 함수 실행

import sys; input=sys.stdin.readline

def w(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)
    
    if (a, b, c) in dp:
        return dp[(a, b, c)]
    
    if a < b < c:
        result = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
    else:
        result = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
    
    dp[(a, b, c)] = result
    return result

dp = {}

for i in range(21):
    for j in range(21):
        for k in range(21):
            w(i, j, k)

while True:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        break
    print(f'w({a}, {b}, {c}) = {w(a, b, c)}')

• pseudo code로 작성되어 있는 재귀 문제를 dp 형식으로 변환하는 문제였습니다.
• 저는 w(20, 20, 20)까지의 결과값을 미리 계산하여 dp로 처리하는 방식을 사용하였습니다.