동전교환

다음과 같이 여러 단위의 동전들이 주어져 있을 때, 거스름돈을 가장 적은 수량의 동전으로 준다면 그 동전의 수는 몇 개인지 구하는 프로그램을 작성하시오. 각 단위의 동전은 무한정 쓸 수 있다.

입력 예제 3 1 2 5 15 출력 예제 3 풀이 코드 가방 문제 최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종... blog.naver.com 위 글에 적어놓은 풀이 방법과 거의 유사하나, 한 가지 다른 점은 동전의 수량을 DP 테이블로 풀이했다. 0 ~ M은 입력 동전 값에 대응하며, 각각의 방은, 값에 대응하는 최소 동전 수량을 의미한다.

이 문제의 입력 예제를 기준으로 하면 배열의 크기는 M+1 (16). 그리고 16개에 달하는 각각의 배열 방은 돈 대비, 거슬러줄 동전의 최소 수량을 나타낸다.

핵심은 거슬러 줄 금액의 최소 동전 수량 = (더 작은 금액의 최소 수량을 만든 최선의 방법) + (동전 1개 ...