문제 번호 2704 --거스름돈 II

2704: 거스름돈 II

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 293  해결 문제 수: 54
[제출][채점상황][게시판][:]

문제 설명

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

입력

첫 번째 줄에는 거슬러 줘야할 돈의 액수가 입력된다. (이 값은 10000원 이하이다.)
다음 줄에는 그 나라에서 사용되는 동전의 종류의 수가 입력된다. (단 동전의 수는 10이하이다.)
마지막 줄에는 동전의 수 만큼의 동전 액수가 입력된다. (동전의 최대값은 10000원 이하이고 정렬되어 있지 않다)

출력

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

입력예시

730
5
10 50 100 500 1250

출력예시

6

도움말

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

출처

[제출][채점상황]