Informatica Online Judge

  거스름돈 II (NTTP) [0167 / 00A7]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 554   Total Tried : 898


The Champion of this Problem (C++) : gs19114 - ms / 342byte
My Best Submission (C++) : N/A

[]

Background

여러분은 실력을 인정받아 전 세계적으로 사용할 수 있는 자동판매기용 프로그램의 개발을 의뢰받았다.
이번에도 역시 자동판매기에서 이용자에게 거스름돈을 남겨줄 때, 거스름돈에 사용될 동전의 개수를 가정 적게하는 것이다.
입력으로 거슬러 줘야할 돈의 액수와 그 나라에서 이용하는 동전의 가지 수 그리고 동전의 종류가 들어온다.
여러분은 그 돈의 액수를 거슬러 주는 여러가지 방법들 중 가장 적은 동전은 몇개인지 구하는 프로그램을 작성해야 된다.

Input

첫 번째 줄에는 거슬러주어야 할 돈의 액수가 입력된다. (이 값은 10000원 이하이다.)

다음 줄에는 그 나라에서 사용 되는 동전의 종류의 가짓 수가 입력된다. (단 동전의 수는 10이하이다.)

마지막 줄에는 동전의 가짓 수 만큼의 동전 액수가 오름차순으로 입력된다. (동전의 최대값은 10000원 이하이다.)

모든 입력에 대해 답이 있음을 보장한다.

Output

최소 동전의 개수를 출력한다.

IO Example

입력
730
5
10 50 100 500 1250

출력
6

설명)
500원 1개, 100원 2개, 10원 3개로 지불하는 것이 최소이다. 따라서 답은 6

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]