[백준] 9184 신나는 함수 실행 파이썬 풀이 (동적계획법)

백준

문제

• a,b,c 중 하나라도 0보다 작으면 1을 리턴한다.
• a,b,c중 하나만 20기 시작하면 w(20,20,20)을 호출한다.
• a<b<c이면 w(a,b,c-1) + w(a,b-1,c-1)-w(a,b-1,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)을 리턴한다.

풀이

• 동적계획법으로 이미 나온 값이 있으면 저장을 해주어야한다. 계속 재귀로 구하지 않도록.
• dp[a][b][c]를 의미하는 3차원 배열을 20길이로 만들어줬다. 20보다 커지면 무조건 dp[20][20][20]을 리턴하기 때문
• def w(a,b,c)함수에 위의 조건을 써주었다.

 

코드

import sys
input = sys.stdin.readline

dp = [[[0]*(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]
    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 1:
    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)}')