[Python] 백준 9184번. 신나는 함수 실행

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

9184번: 신나는 함수 실행

문제 설명:

재귀 함수로 실행을 하고 있지만 시간이 너무 걸린다는 문제가 있다.

 

풀이 방법:

dp, 메모이제이션으로 풀어본다.

재귀함수는 일반적으로 연산에 대한 결과를 저장하고 있지 않아 같은 값의 연산도 다시 수행되어야 하는 문제가 있다.

이를 기억하고 있다가 만약 그 숫자들에 대한 연산이 필요하면 값을 꺼내와서 반환하도록 한다.

• 20보다 크면 무조건 20을 반환하기 때문에 배열은 21을 최대 길이로 설정한다.

 

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 True:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        break
    answer = w(a, b, c)
    print("w({0}, {1}, {2}) = {3}".format(a, b, c, answer))