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

주어진 재귀 함수를 동적 계획법으로 푸는 문제다. 처음에 봤을 때는 이전에 풀었던 피보나치 문제처럼 규칙이 있으면, append 해주면서 풀면 되겠구나 싶었지만, 딱히 규칙같은건 없었다. 재귀 함수를 보면, a,b,c의 입력이 -50~50이고, 21~50은 20,20,20으로 대체되고, -50~0은 1이 리턴되기 때문에 생각해야할 것은 1~20일 때다. 구한 값을 a= 1, b=1, c=1부터 a=20, b=20, c=20까지 총 20*20*20의 8000개의 배열이 필요할 것이다. 넉넉하게 10000개의 배열을 0으로 초기화하여 선언한다. 그 뒤 index를 계산해보면, 인덱스는 (a - 1) * 400 + (b - 1) * 20 + (c - 1)이 나온다. 만약 w[index]에 값이 없으면 캐싱해주고 다시 재귀해주면 되겠다. 

 

##함수 선언 부분##
def W(a, b, c):
    index = (a - 1) * 400 + (b - 1) * 20 + (c - 1) #구한 값을 캐싱하기 위한 index
    if a <= 0 or b <= 0 or c <= 0: 
        return 1
    elif a > 20 or b > 20 or c >20:
        return W(20, 20, 20)
    elif (a < b) and (b < c):
        if w[index] == 0: #값이 캐싱되어있지 않으면
            w[index] = W(a,b,c-1) + W(a,b-1,c-1) - W(a,b-1,c) #값을 저장

        return w[index]
    else:
        if w[index] == 0:
            w[index] = 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 w[index]
##변수 선언 부분##
w = [0]*10000

##메인 함수 부분##
if __name__ == "__main__":
    while True:
        a, b, c = map(int,input().split())
        if a == b == c == -1:
            break
        else:
            ans = W(a,b,c)
            print("w(%d, %d, %d) = %d"%(a,b,c,ans))

피보나치 문제가 Bottom-up 방식이었다면 이 문제는 Top-down 방식이다. 재귀함수 내에서 값을 메모이제이션해주는 것이 중요하다. 처음엔 감도 안왔지만 동적 계획법의 특징을 생각하면 간단하게 풀 수 있었던 문제다.