백준 9184 파이썬 - 신나는 함수 실행 - 동적 계획법

백준 9184 파이썬

https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

문제에서 위와 같은 조건의 재귀함수가 주어지는데... 해당 재귀를 그대로 실행하면 값을 구하는데 너무 오래 걸린다고 한다. 동적 계획법의 기원? 동적 계획법이란 알고리즘이 생겨나게 된 배경이... 분할정복에서 작업들을 쪼개서 할 때 중복되서 하는 작업이 많은 문제를 해결하기 위해 만들어졌다고 합니다.

 

그래서 재귀함수와 같이 뎁스를 타고 내려가서 값을 구할 때... 계산한 값을 중간에 확인하는 분기를 주면, 불필요한 계산을 줄이고 이전에 계산한 값을 사용할 수 있습니다.

 

 

Python 풀이

import sys
read = sys.stdin.readline

cache = {}

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)
        
    key = '{} {} {}'.format(a, b, c)
    
    ### 핵심코드 ###
    if key in cache:
        return cache[key]
    res = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
    cache[key] = res
    ################
    
    return res

while True:
    a,b,c = map(int, read().split())
    if a == -1 and b == -1 and c == -1:
        break
    print('w({}, {}, {}) = {}'.format(a, b, c, w(a, b, c)))

• 주어진 w 함수에서 중간에 계산된 값을 저장하고 재사용할 수 있는 분기를 준다.(핵심 코드)
• 값을 저장하기 위한 cache를 딕셔너리 형태로 선언하고 a,b,c를 이용해서 string 형태로 만들어 key값으로 사용한다.
  • 다른 풀이로는 딕셔너리가 아니라 메모이제이션을 3차원 배열을 이용해서 푸는 방법도 있습니다.