[백준 #9184] 신나는 함수 실행 - 파이썬(python)

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

동적계획법,, 너무 어렵다,,

문제 자체에 점화식을 써 준것인지도 몰랐다.

 

아직 너무 아무것도 몰라서 결국 다른분 풀이를 보고 참고했다.

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]

Max=21
dp=[[[0]*Max for _ in range(Max)] for _ in range(Max)]
while True:
    a,b,c=map(int,input().split())
    if a==-1 and b==-1 and c==-1:break
    val=w(a,b,c)
    print("w({}, {}, {}) =".format(a,b,c),val)

이 전에는 리스트 값에 연산값을 저장하더라도 연산할 때 마다 초기화해서 

새로운 값으로 저장하는 방식을 썼었는데,

연산하는 모든 값을 저장해서 그 값으로 더 큰 문제의 해를 구하는 방법이

아직 익숙하지가 않다.

 

좀 더 공부해서 어서 내것으로 만들어야지!