[백준/9184/파이썬] 신나는 함수 실행

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

9184번: 신나는 함수 실행

Problem

• 재귀 호출만 생각하면 신이 난다! 아닌가요? 네 아니에요
• 다음과 같은 재귀함수 w(a, b, c)가 있다.

조건

최적화를 하세요!

SOL

메모이제이션을 할줄아냐? 물어보는 간단한 문제이다.

import sys
sys.setrecursionlimit(10**6)
DP=[[[0]*21 for _ in range(21)] for _ in range(21)]

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 DP[a][b][c]:
        return DP[a][b][c]
    if a<b<c:
        DP[a][b][c]= w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return DP[a][b][c]
    DP[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 DP[a][b][c]

while True:
    a,b,c =map(int,input().split())
    if a== -1 and b==-1 and c==-1:
        break
    print("w(%d, %d, %d) = %d"%(a,b,c,w(a,b,c)))