126. 9184 (신나는 함수 실행)

TOP - DOWN 방식

result = ""
memo = [[[0 for _ in range(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 memo[a][b][c] > 0 :
        return memo[a][b][c]  
    
    if a < b < c :
        memo[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return memo[a][b][c]  
    
    memo[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 memo[a][b][c]
    

while True:  
    a,b,c = map(int, input().split())
    
    if a == -1 and b == -1 and c == -1:
        break
    
    tmp = w(a,b,c)
    
    result += ("w({}, {}, {}) = {}".format(a,b,c,tmp)) + "\n"

print(result)

문제요약

재귀함수를 동적프로그래밍으로 바꾸는 문제

설명

동적프로그래밍을 알면 크게 어렵지 않다.

동적프로그래밍의 개념은 아래를 참고하자.

https://smhope.tistory.com/328?category=1056187 

동적프로그래밍(Dynamic Programming)

    if memo[a][b][c] > 0 :
        return memo[a][b][c]

메모에 기입되있다면 넘어간다.

 

    result += ("w({}, {}, {}) = {}".format(a,b,c,tmp)) + "\n"

문자열을 저장할 때 다음과 같이 저장이 가능하다.