[백준2294&파이썬] DP를 이용하여 동전교환문제를 해결하기, DP는 값을 재활용한다.

# 문제

백준 2294 동전2 파이썬 풀이

2294번: 동전 2

# 코드

'''
  - DP배열을 -1로 초기화 해주는게 좋을 듯 하다.
    - 만일 중간에 0인 지점이 있을텐데 그 지점은 못와서 0일텐데 이걸 체크 안하면 그다음은 여기에 1더해버리기 때문이다.
    - 문제에서 나름 불가능할경우 -1을 출력하라는거에서 힌트처럼 느껴질수도..
'''
import sys

coins = list()
n,k = map(int,sys.stdin.readline().split())
for _ in range(n) :
  coin = int(sys.stdin.readline().strip())
  coins.append(coin)

dp = [-1] * (k+1) # 메모이제이션을 위한 배열
dp[0] = 0

for i in range(k+1) :
  minimum = float('inf')
  for coin in coins :
    before = i - coin
    if 0 <= before and dp[before] != -1:
      minimum = min(minimum, dp[before] + 1)
      dp[i] = minimum

print(dp[k])

# 풀이

• DP를 이용한 동적프로그래밍은 이전에 계산했던 값을 재활용함으로써 계산 시간을 단축시킨다. 피보나치 수열을 구하는 예를 생각해보면 된다.
• 해당 문제에서는 동전의 최소 개수를 묻는다. 만일 10원을 동전 3개를 사용해서 만든게 최소라면, 11원은 10원에 1원 동전 하나만을 사용해서 만들 수 있다. 10원이 이미 최소값임을 보장하기 때문에, 11원또한 동전 한개만 사용한다면 최솟값임이 보장된다. 
• 처음 문제를 풀때 dp배열을 아무생각 없이 0으로 초기화 했었다. dp[0]은 당연히 0일테지만, 중간에 등장하는 0의 의미는 다르다. 중간에 등장하는 dp[n]이 0이라는 의미는 해당 n원은 동전을 사용해서 만들 수 없다는 뜻을 가질 수 도 있다. 그렇기 때문에 n원일때는 계산하지 않도록 해야한다.
• 이 문제를 dp를 -1로 초기화 한 다음에, dp[before] != -1 일때만 계산하도록 수정하여 해결했다.