백준 9184 파이썬(DP - 메모이제이션)

메모이제이션을 이용해서 풀어야 하는 DP 문제다.

3차원 리스트를 이용하면 쉽게 풀 수 있다.

# 9184 - 신나는 함수 실행
dp = [[[0]*21 for _ in range(21)] for __ in range(21)]
 
def w(a, b, c) :
    print(dp)
    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]

import sys
input = sys.stdin.readline
while True:
    a,b,c = map(int,input().split())
    memo = {}
    if a == -1 and b == -1 and c == -1:
        break
    
    print(f'w({a}, {b}, {c}) = {w(a,b,c)}')

 

이 코드는 3차원 리스트가 아니라 딕셔너리를 이용해서 메모이제이션을 구현해봤다.

구현하는 방식만 다를뿐 아이디어나 알고리즘 원리는 같다.

# 9184 - 신나는 함수 실행
def w(a,b,c):

    if a <= 0 or b <= 0 or c <= 0:
        return 1
    elif a > 20 or b > 20 or c > 20:      
        return w(20,20,20)
    elif (a,b,c) in memo:
        return memo[(a,b,c)]
    elif 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)]

memo = {}
import sys
input = sys.stdin.readline
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)}')