백준 22.02.05. 9184번 - 신나는 함수 실행

import sys
input = sys.stdin.readline


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] != 0:
        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]


dp = [[[0 for _ in range(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
    print("w({}, {}, {}) = {}".format(a, b, c, w(a, b, c)))

• 우선 함수식은 문제에 주어진대로 만들었습니다.
• a,b,c를 좌표라고 생각하고 w함수에 a,b,c를 할당하여 나온 값을 해당 좌표의 값으로 지정할 것입니다.
  • 주어진 식에서 0 ≤ a,b,c ≤ 20 의 범위를 가지므로 21³의 크기를 갖는 3차원 배열을 만들어줍니다.
  • 주어진 a,b,c를 w함수에 할당하여 나온 값을 dp[a][b][c]에 저장할 것입니다.
    
    • 매 번 재귀를 사용하지 않고 함수를 실행하여 나온 값을 리스트에 저장하여 재활용할 수 있도록 하는 것이 다이나믹 프로그래밍입니다.
• 0보다 작으면 1을 반환하고 a,b,c 중 하나라도 20보다 크다면 a,b,c를 20으로 조정하여 재귀를 실행합니다.
• 만약 dp[a][b][c]에 0이 아닌 값이 할당되어 있다면 이미 계산이 된 좌표이므로 그대로 반환합니다.
• 이하는 문제에 주어진 식을 그대로 활용하였습니다.