신나는 함수 실행 [백준 9184] - python

import sys
input = sys.stdin.readline

def BOJ9184() :
  dic = {}
  def w(a,b,c) :
    if (a,b,c) in dic :
      return dic[(a,b,c)]
    
    if a <= 0 or b <= 0 or c <= 0 :
      dic[(a,b,c)] = 1
      return dic[(a,b,c)]

    if a > 20 or b > 20 or c > 20 :
      return w(20, 20, 20)
    
    if a < b and b < c :
      dic[(a,b,c)] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
      return dic[(a,b,c)]
    
    else :
      dic[(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 dic[(a, b, c)]
    

  while True :
    a,b,c = map(int, input().split())
    if a == -1 and b == -1 and c == -1 :
      break
    print(f"w({a}, {b}, {c}) = {w(a,b,c)}")
    

BOJ9184()

 

이 문제를 포스팅 하게 된 이유는 재귀함수에서의 메모이제이션에 대해 포스팅 하고 싶어서였다. 

코드 상의 

if (a,b,c) in dic :
      return dic[(a,b,c)]

위의 내용을 통해 해당 재귀함수가 호출되기전 값의 유무를 검사하게 된다.

 

딕셔너리에 키값을 세개의 숫자 조합으로 넣어주었고 (삼차원 배열로 줄수도 있었지만 메모리 제한 + 시간 효율로 dict를 선택하였다)

값을 조회하여 값이 존재하게 되면 불필요한 재귀함수를 호출하지 않아도 되어 시간을 save 해준다.

 

 

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

9184번: 신나는 함수 실행