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

문제링크

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

9184번: 신나는 함수 실행

---

 

코드

dp = [[[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 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]
    else:
        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(f'w({a}, {b}, {c}) =',w(a,b,c))

---

 

문제풀이

문제에 나와있는대로 a,b,c가 0보다 작거나 같으면 1을 return해주고

a,b,c가 20보다 크면 w(20,20,20)을 return 해준다. 

따라서, 크기가 20인 3차원 리스트만 만들면 된다. 리스트에 이미 저장되어 있다면 그 값을 return하고

저장되어 있지 않다면 값을 구하고 리스트에 저장한 후 return해준다.