동전교환 > 문제은행

본문 바로가기


알고리즘 다이나믹1

2000 : 동전교환

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 1879 회    시도횟수: 6750 회   



우리나라 동전의 단위는 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개 필요하다.


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

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


첫 줄은 동전의 단계 수 N(1≤N≤10), 둘째 줄은 N개로 이루어진 동전들의 단위들이며, 셋째 줄은 잔돈 W(1≤W≤64,000)을 나타낸다.



첫 줄에 잔돈을 맞추기 위한 최소의 동전 수를 출력한다. 만약 동전을 맞추기가 불가능한 경우는 "impossible"을 출력한다.


[Copy]
3
1 4 6
8
[Copy]
2


4원짜리 2개가 8원을 만들기 위한 최소의 동전 수이므로 답은 2이다.




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.