백준 9148 : 신나는 함수 실행 (Python)

본문 링크

import sys
input=sys.stdin.readline

def Recursion(a,b,c):
    if a<=0 or b<=0 or c<=0:
        return 1
    if a>20 or b>20 or c>20:
        return Recursion(20,20,20)
    if dp[a][b][c]:
        return dp[a][b][c]
    if a<b<c:
        dp[a][b][c]=Recursion(a,b,c-1)+Recursion(a,b-1,c-1)-Recursion(a,b-1,c)
        return dp[a][b][c]
    else:
        dp[a][b][c]=Recursion(a-1,b,c)+Recursion(a-1,b-1,c)+Recursion(a-1,b,c-1)-Recursion(a-1,b-1,c-1)
        return dp[a][b][c]


dp = [[[0] *21 for _ in range(21)] for _ in range(21)]

while True:
    a,b,c=map(int,input().split())
    if a==-1 and b==-1 and c==-1:
        break
    else:
        print("w(%d, %d, %d) = %d"%(a,b,c,Recursion(a,b,c)))

📌 어떻게 접근할 것인가?

문제 그대로 코드를 구현하면 된다.
다만 재귀를 통해 함수가 작동하므로 메모제이션 방법을 사용해야한다.
그대로 구현하면 시간초과가 나니깐 주의하자.

dp = [[[0] * 21 for _ in range(21)] for _ in range(21)] 로 3차원 배열을 잡고

만약 이미 방문했다면 return dp[a][b][c] 을 해준다. 이 부분이 코드 실행을 단축시켜준다.