문제
여러분은 실력을 인정받아 전 세계적으로 사용할 수 있는
자동판매기용 프로그램의 개발을 의뢰받았다.
거스름돈에 사용될 동전의 수를 최소화하는 것이다.
입력으로 거슬러 줘야할 돈의 액수와
그 나라에서 이용하는 동전의 가짓수 그리고 동전의 종류가 입력되면
여러 가지 방법들 중 가장 적은 동전의 수를 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 거슬러 줘야할 돈의 액수 m이 입력된다.
( 10 <= m <= 10,000 )
다음 줄에는 그 나라에서 사용되는 동전의 종류의 수 n이 입력된다.
( 1 <= n <= 10 )
마지막 줄에는 동전의 수만큼의 동전 액수가 오름차순으로 입력된다.
( 10 <= 액수 <= m)
출력
최소의 동전의 수를 출력한다.
예제
730
5
10 50 100 500 1250
6
출처
문제해결을 위한 창의적 알고리즘 (고급), comkiwer
로그인해야 코드를 작성할 수 있어요.