BOJ - 2294 ) 동전 2

BOJ - 2293) 동전 1의 변형 문제이다. 동전 1의 경우, 주어진 금액을 나타내는 최대의 경우의 수를 출력하는 반면 동전 2의 경우 최소 경우의 수로 해당 금액을 나타내는 문제이다. 주의하여 생각해야할 점은 동전 1과 큰 차이가 없다.

 

1. 동전 1과 같이, 동전의 종류 별 경우의 수를 갱신한다.

2. 경우의 수를 갱신할 때, 배열 d 의 인덱스 값보다 적은 가치의 동전만을 생각한다.

3. 기존의 배열 d의 값과, 도출된 d 의 값을 비교하여, 적은 값을 선택한다.

4. 주어진 k 값이 도출되지 않을 경우(값이 갱신되지 않았을 경우) -1 을 출력한다.

 

d[j] 의 값을 갱신할 때마다 기존의 d[j] 의 값과  배열에서 동전의 가치만큼 뺀 뒤 1을 더해준 값과 비교하여 더 작은 값을 갱신하고, 값이 갱신이 되지 않았다면 -1 을 return 한다. 

ex) i = 1 의 경우, 출력 배열인 d 의 값은 등차가 1인 수열 형태를 띄게 된다. (cost[1] = 1)

i = 2, j= 5 의 경우, min (d[5], d[5 - 5] + 1) 에 따라 d[5] 의 값이 1로 갱신된다.