우리나라 동전의 단위는 1원, 5원, 10원, 50원, 100원, 500원의 6단계로 이루어진다.

잔돈 256원을 내주려면 500원 0개, 100원 2개, 50원 1개, 5원 1개, 1원 1개로 해서 모두 5개의 동전이 필요하다.

만약 동전 단위가 1원, 4원, 6원의 3단계로 이루어진 나라에서 8원을 내주려면 6원 1개, 1원 2개도 가능하고,

4원 2개로 가능하다. 앞의 경우에는 동전 3개, 뒤의 경우에는 동전이 2개 필요하다.

동전의 개수를 최소로 하면서 동전을 내주는 것이 목적이라면 뒤의 방법을 택해야 한다.

동전의 단위들이 주어지고, 원하는 잔돈이 주어질 때, 그 잔돈에 맞추기 위해 필요한 최소의 동전 수를 구하시오.

갖고 있는 동전의 수는 무한하다.

동전교환 timer 1초 memory 64MB

동전교환 1초 64MB