[python] 9184. 신나는 함수 실행

• 문제 

 

 

• 올바른 풀이

import sys

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 and b < c:
        dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
    else:
        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
    print('w({}, {}, {}) = {}' .format(a, b, c, w(a, b, c)))

 

해당 문제는 재귀 문제로, 다이나믹 프로그래밍 자료구조 방법으로 문제를 해결한다. 

다이나믹으로 문제를 해결하면, 한 번 계산한 값을 저장하고 불러오기 때문에 다시 계산하지 않아도 된다. 

이로써 연산시간이 크게 감소할 수 있는 것이다.