[동적 계획법] 신나는 함수 실행

동적 계획법의 핵심은 return 값의 재사용.

 

재사용 할 값을 어떻게 효율적으로 저장 및 탐색할 수 있는지에 대한 고민과 그에 따른 자료구조 선택이 중요한 것 같다.

 

9184번: 신나는 함수 실행

from sys import stdin

w_dict = {}

input_abc_arr = []

while True:
    [a, b, c] = map(int, stdin.readline().split())
    if a == -1 and b == -1 and c == -1:
        break
    else:
        input_abc_arr.append([a, b, c])


def w(a: int, b: int, c: int):
    global w_dict

	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 f'{a},{b},{c}' in w_dict:
        return w_dict[f'{a},{b},{c}']
    else:
        if a < b < c:
            abc = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
        else:
            abc = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1)

        w_dict[f'{a},{b},{c}'] = abc
        return abc


for _input in input_abc_arr:
    [a, b, c] = _input
    answer = w(a, b, c)
    print(f'w({a}, {b}, {c}) = {answer}')