[Algorithm] 1일1솔 - 백준 9184 신나는 함수 실행 (python3)

문제링크

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

9184번: 신나는 함수 실행

문제설명

문제에 재귀 함수 코드가 주어져 있고, 그대로 구현하면 값을 구하는 데 시간이 매우 오래 걸린다는 힌트도 주고 있다.

따라서 메모이제이션으로 풀어야 함을 알 수 있고, 이 때 0 이하인 수는 1, 20 초과인 수의 경우는 모두 w(20,20,20) 이므로 초기값은 20까지 설정해두면 된다.

문제풀이

a, b, c가 모두 같을 경우 a, b, c가 0 이하가 될 때까지 재귀를 돌게 되어 시간이 매우 오래 걸리므로, 메모이제이션을 활용하여 풀이했다.

0~20 범위로 메모이제이션 배열 memo 를 만들어 초기값 0으로 설정하고, 0 이하일 경우부터 고려해준 후 memo 배열에 a,b,c 에 해당하는 값이 있으면 리턴한다.

import sys
input = sys.stdin.readline

memo = [[[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 memo[a][b][c]:
        return memo[a][b][c]
    if 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]

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