알고리즘 다이나믹프로그래밍 동전 문제 2

흔히 DP라고 하는 다이나믹프로그래밍 문제중에

가장 기본적인 문제가 동전 문제이다.

만들어야 할 금액과 동전의 종류가 주어졌을 때  

동전들을 최소의 개수로 조합해서 금액을 만들면 되는 문제이다.

예를들어 만들어야 하는 금액이 15원이고

주어진 동전의 종류가 1원, 5원, 12원이면(동전은 여러번 사용해도 된다.)

15원을 만들 수 있는 동전의 최소의 개수는 3이다. (5원+5원+5원)

이 문제를 푸는 핵심은 다음과 같다.

1. 다이나믹 테이블 D[]를 필요한 동전의 개수를 저장하는 배열로 선언

    예) D[15] = 15원을 만드는 데 필요한 동전의 개수

2. 다이나믹 테이블 D[]는

    만들어야 할 금액에서 추가할 동전의 금액을 뺐을 때

    예를 들어 15원-5원은 10원이므로

    10원을 만드는 데 필요한 동전의 개수에 한개를 더한 값

    15원을 만드는 데 필요한 동전의 개수를 비교하여 

    최소값을 택하는 방식으로 다이나믹 테이블을 만들어간다.

   다이나믹 테이블이 만들어지는 방식을 간단히 정리해 보면 다음과 같다.

   D[5], D[5-1]+1

   D[5], D[5-5]+1 ==> D[5]는 초기에 MAX값으로 설정되어 있으므로 D[5-5]+1=D[0]+1=0+1=1이 최소값

   D[10], D[10-1]+1

   D[10], D[10-5]+1 ==> D[10-5]+1=D[5]+1=1+1=2

   D[10], D[10-12]+1

위의 내용을 코드로 작성해 보면 다음과 같다.