[알고리즘] Coin Exchange Problem2.

목표 : 목표 금액 'A'와 n개의 동전이 주어질 때(v1 < v2 < v3 < ..... < vn), 목표 금액 'A'에 대한 잔돈을 만들 때 필요한 동전의 최소 개수를 찾는 프로그램을 작성하라.

목표 금액 = 5

동전[] = 1, 2, 3

동전을 만들 수 있는 방법의 수 = { 1, 1, 1, 1, 1 }, { 1, 1, 1, 2 }, { 2, 2, 1 }, { 1, 1, 3 }, { 3, 2 }

최소 동전의 수 { 3, 2 } => 2개

모든 동전과 관련하여 두 가지 옵션이 있다.(동전을 선택할지 말지) 따라서 두 가지 옵션을 모두 고려한 솔루션을 찾아서 최적 해를 선택해야 한다. 이번 문제의 경우는 모든 솔루션 중 최소인 것을 고르면 된다. 

먼저, 문제를 더 작은 문제들로 분해한다. 그러면 더 작은 문제는 뭘 뜻할까?

목표 금액은 'A'이며, 동전은 v1, v2, v3, .... , vn이라고 하자.

MC(j)는 목표 금액 j에 대한 잔돈을 만들 때 요구되는 동전의 최소 개수.

더 작은 문제

1) 첫 번째 동전(v1)을 선택, 이제 더 작은 문제는 목표 금액 [(j - v1), MC(j - v1)]에 대한 잔돈을 만들 때 요구되는 동전의 최소 개수다.

2) 두 번째 동전(v2)을 선택, 이제 더 작은 문제는 목표 금액 [(j - v2), MC(j - v2)]에 대한 잔돈을 만들 때 요구되는 동전의 최소 개수다.

3) 이 같은 방식으로 N까지 이어진다.

4) N 번째 동전(vn)을 선택, 이제 더 작은 문제는 목표 금액 [(j - vn), MC(j - vn)]에 대한 잔돈을 만들 때 요구되는 동전의 최소 개수다.

우린 목표금액 j에 대한 잔돈을 만들 때 요구되는 동전의 최소 개수를 찾을 필요가 있다. 따라서 더 작은 문제에 대한 최소 동전 개수를 선택하게 될 것이며 동전 하나를 추가한다는 의미로 1을 더하게 된다. 이처럼 더 작은 문제는 재귀적으로 해결해 나간다.

따라서 재귀 방정식을 작성하면 다음과 같다.

** Using Bottom-Up Dynamic Programming **

상향식 다이나믹 프로그래밍

1) 부분 문제에 대한 최적해를 저장할 배열을 관리하며, 그 배열을 coinReq[]라 한다. 이 배열의 길이는 amount + 1(0부터 시작)이다.

2) 따라서 coinReq[n]이 최종해가 된다. 목표 금액(n)에 대한 잔돈을 만들 때 필요한 동전의 최소 개수.

3) 상향식(Bottom-up) 방법을 사용하므로, coinReq[]를 0부터 n까지 채워야 한다. 

4) 0원을 만들기 위해선 그 어떤 동전도 필요하지 않으므로 coinReq[0] = 0이다.

5) 또 다른 배열인 CC[](크기 : 동전의 수)도 이용할 것이며, 모든 동전을 이용하여 목표금액 n에 대한 해를 저장할 것이다. 이 중에 가장 작은 값이 목표 금액에 대한 최적해가 될 것이다.

6) 0부터 N까지의 금액에 대한 최적해를 찾아야 하기 때문에, CC[] 배열을 매번 리셋해야 한다.

7) 아래 코드를 살펴보자.