백준 9184번 신나는 함수 실행 (Python)

문제에 점화식까지 쓰여있어서 당황스러웠다..

너무나도 당연하게 문제에 쓰여져있는대로 코드를 작성하면 안된다!

재귀함수를 사용해야할 때 이것을 메모이제이션 하는 방법을 묻는 문제이다.

MAX = 21
dp = [[[0]*MAX for _ in range(MAX)] for __ in range(MAX)]
 
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)))

문제링크 : https://www.acmicpc.net/problem/9184

메모이제이션 : https://namu.wiki/w/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98