[백준 2024/03/19] 9184번 신나는 함수 실행

https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

 

1. 접근 방법

처음에 고민을 하다가, w(1, 1, 1)의 값은 동일할 것이고, 코드를 실행하면서 해당 값의 필요성이 중복될 것이라 생각이 들었다.

따라서 memoization을 사용해야겠다고 생각이 들었다.

 

dict_r = {} 라는 dictionary를 만들고, 

만약 특정 값이 dictionary에 저장되어 있으면, 바로 해당 값을 return 해주었으며

없다면, 그 값을 구하고 딕셔너리에 없는 값이 구해졌을 땐, dictionary에 해당 값을 추가해주었다.

 

2. 코드

x, y, z = map(int, input().split())

dict_r = {}


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

    return dict_r[(a, b, c)]


while x != -1 or y != -1 or z != -1:
    print("w({a}, {b}, {c}) = {d}".format(a=x, b=y, c=z, d=f(x, y, z)))
    x, y, z = map(int, input().split())