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

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

---

문제요약

재귀 함수를 다이나믹 프로그래밍으로 구현하기

풀이

식이 모두 주어줘 있는 재귀 함수이므로 다이나믹 프로그래밍만 구현해주면 된다.

다이나믹 프로그래밍에서 가장 중요한 점은 "이미 계산했던 값은 다시 계산하지 않는다."이다.

그래서 dp라는 리스트를 만들어 계산했던 값은 저장해 주면 된다.

dp 리스트를 선언할 때 인풋값의 범위가 -50 ~ 50 이므로 사이즈를 102로 하였다. 음수값이 들어오더라도 리스트의 뒤의 값부터 인덱싱을 하기 때문에 추가적인 코드를 짤 필요는 없다. 

---

소스코드는 Python 3으로 작성되었습니다.

import sys

input = sys.stdin.readline
dp = [[[False for _ in range(102)] for _ in range(102)] for _ in range(102)]


def func_w(a, b, c):
	# 만약에 이미 dp에 값이 있다면(파이썬에서 int는 True 값이다.) dp 리스트의 값을 반환
    if dp[a][b][c]:
        return dp[a][b][c]
    if a <= 0 or b <= 0 or c <= 0:
        dp[a][b][c] = 1
        return dp[a][b][c]
    if a > 20 or b > 20 or c > 20:
        dp[a][b][c] = func_w(20, 20, 20)
        return dp[a][b][c]
    if a < b and b < c:
        dp[a][b][c] = func_w(a, b, c - 1) + func_w(a, b - 1, c - 1) - func_w(a, b - 1, c)
        return dp[a][b][c]
    dp[a][b][c] = func_w(a - 1, b, c) + func_w(a - 1, b - 1, c) + func_w(a - 1, b, c - 1) - func_w(a - 1, b - 1, c - 1)
    return dp[a][b][c]


while True:
    a, b, c = map(int, input().split())
    if a == b == c == -1:
        break

    func_w(a, b, c)

    print('w(%d, %d, %d) = %d' % (a, b, c, dp[a][b][c]))