[9184번] 신나는 함수 실행

백준 9184번 신나는 함수 실행

코드 풀이

import sys
sys.setrecursionlimit(10**5)


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


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

while True:
    a, b, c = map(int, sys.stdin.readline().split(' '))
    if a == -1 and b == -1 and c == -1:
        break
    result = w(a, b, c)
    print("w({0}, {1}, {2}) = {3}".format(a, b, c, result))

• 위 재귀함수의 성능 문제는 구했던 값을 반복해서 구하는 것에 있습니다.
• 따라서 한 번 구한 값을 저장할 수 있는 공간(dp)을 만들어서 계산의 결과값을 저장합니다.
• 다음에 그 값을 이용해야 할 일이 있을 때, 계산이 아닌 저장된 값을 사용하면 됩니다.
• 원소가 하나라도 20 이상이 되면 w(20, 20, 20)으로 통일되므로, 0~20 크기의 3차원 배열 변수를 만들면 됩니다.