[BOJ] 2294번: 동전 2

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

D[i]를 가치 i를 만들 수 있는 동전의 최소갯수라고 합시다.(만들 수 없는 경우에는 1000000을 넘는 값이 들어가있어야 함)

이 때 동전을 하나씩 추가하며 동전 i=0~n에 대해 j=0~k를 D[j] = min(D[j], D[j-coin[i]]+1)으로 갱신해줍니다. 그러면 최종적으로 D[k]에는 동전을 전부 사용했을 때 가치 k를 만들 수 있는 동전의 최소갯수가 저장됩니다. 만약 1000000을 넘는 값이 들어가있을 경우 -1로 바꾸어 출력하면 됩니다.

https://github.com/encrypted-def/BOJ/blob/master/2294.cpp