백준 9184번: 신나는 함수 실행 python

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

문제 접근

재귀함수 w(a,b,c)를 출력하는 프로그램을 구현해야한다.
우선 재귀함수 w(a,b,c) 를 이해해보자.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1 
# a,b,c 중 하나라도 0 이하이면 1을 리턴한다.

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)
# a,b,c 중 하나라도 20보다 크면 w(20,20,20) 함수를 리턴한다.

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
# a<b<c 라면 w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c) 를 리턴한다.

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
# 다 아니라면 저것을 리턴한다.

# 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

그냥 이것을 파이썬으로 구현하면 다음과 같다.

import sys
sys.setrecursionlimit(100000)  # 재귀 깊이 제한을 늘려줌

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 a < b and b < c:
        return w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
    else:
        return w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

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

그러나 함수가 계속 재귀적으로 호출하기 때문에 그냥 무지성 재귀호출을 하면 안된다.

a, b, c가 20보다 크면 w(20, 20, 20)을 호출하고,

음수거나 0보다 작으면 1을 반환해야 한다.

이를 메모이제이션이라고 한다.
이를 활용하여 풀면

import sys
input = sys.stdin.readline

dp = [[[0]*(21) for _ in range(21)] for _ in range(21)]
# 0~20까지므로

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]
    # 조건 a < b < c에 해당되면 이 공식 사용
    # 결과 계산하고 dp에 저장 후 반환
    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]
    # 나머지 경우엔 이 공식 사용해서 계산 후 dp에 저장하고 반환


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)}')

가 된다. 이미 갔던 길이면 저장해놓고 저장된것을 사용하는 것이 핵심.