백준 9184-신나는 함수 실행

문제

알고리즘 분류)

• 다이나믹 프로그래밍
• 재귀

풀이

주어져있는 함수를 그대로 이용하면 w(15,15,15)에서 2분이 넘도록 실행된다
3차원배열을 만들어
함수를 그대로 이용하면서 메모이제이션으로 이전에 구한 결과값을 저장해놓으면 되었다

소스코드

python)

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

def fuct(a,b,c):
    if a<=0 or b<=0 or c<=0:
        return 1
    elif a>20 or b>20 or c>20:
        return fuct(20,20,20)
    elif array[a][b][c]:
        return array[a][b][c]
    elif a<b and b<c:
        array[a][b][c] = fuct(a,b,c-1)+fuct(a,b-1,c-1)-fuct(a,b-1,c)
        return array[a][b][c]
    else:
        array[a][b][c] = fuct(a-1,b,c)+fuct(a-1,b-1,c)+fuct(a-1,b,c-1)-fuct(a-1,b-1,c-1)
        return array[a][b][c]
    
while True:
    a,b,c = map(int, input().split())
    if a==b==c==-1:
        break
    print("w({0}, {1}, {2}) = {3}".format(a,b,c,fuct(a,b,c)))