[백준] Python [9184] 신나는 함수 실행

 

 

 

 

이 문제는 재귀 함수를 메모이제이션(Memoization)을 추가하여 이전에 계산한 적 있는 입력 값을 저장하여 같은 연산을 반복하지 않도록 하여 시간을 단축하는 문제이다.

 

Python에는 dictionary를 사용하여 동적 계획법을 쉽게 해결할 수 있다. dictionary는 key와 value를 짝지어 값을 저장한다. key값으로 int, string, float 등을 사용할 수 있으며 이번 문제에서 변수를 a, b, c 3개를 사용하므로 a, b, c를 tuple 안에 넣어서 키값으로 이용했다.

import sys

d = {}


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


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