백준 알고리즘 9184 [파이썬]

배운 내용

이 문제는 동적 계획법(DP)를 사용해서 풀어야 하는 문제이다. 동적 계획법으로 문제를 풀어봤지만 이번 문제를 통해서 동적 계획법이 무엇인지 정확하게 이해할 수 있었다. 

동적 계획법 (Dynamic Programming)

동적 계획법은 재귀적으로 함수가 계속 실행될 때 소요 시간을 줄여주기 위해서 새로운 문제 값을 저장하고 해당 문제값이 저장되어있으면 다시 계산해서 그 값을 얻어내는게 아니라 미리 저장해두었던 값을 사용함으로써 재귀적으로 함수가 실행되는 시간을 대폭 줄여준다. 

 

동적 계획법에도 여러가지 방법이 있는것으로 알고 있는데, 이 문제에서는 문제 값을 저장할 공간(리스트 또는 딕셔너리)을 만들고 그 곳에다 저장하고 필요할 때 사용한다.

 

 

 

문제 

 

문제풀이

from sys import stdin
read = stdin.readline
# 해당 키값에 맞는 value값을 memo라는 딕션너리에 저장한다.
memo = {

}

def w(a, b, c):
  # 만약에 memo안에 같은 key값이 있으면 value값을 가져와서 리턴한다.
  if (a, b, c) in memo:
    return memo[(a, b, c)]

  elif a <= 0 or b <= 0 or c <= 0:
    return 1
  
  elif a > 20 or b > 20 or c > 20:
    return w(20, 20, 20)

  # 새로운 key값과 value값들을 메모에 저장하고 value값을 리턴한다.
  elif a < b and b < c:
    w_num = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
    memo[(a, b, c)] = w_num
    return w_num
  
  else: 
    w_num = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
    memo[(a, b, c)] = w_num
    return w_num

while True:
  a, b, c = map(int, read().split())
  # a, b, c 값 모두가 -1 때 입력을 마지막으로 해야하기 때문에 while loop을 break한다.
  if a == -1 and b == -1 and c == -1 :
    break
  # %d를 사용해서 ''안에 필요한 지정값을 넣어줄 수 있다.
  print('w(%d, %d, %d) = %d' % (a, b, c, w(a, b, c)))

문제풀이 영상