자동판매기
면접 대비시간 제한8초메모리 제한512 MB
최대 10가지 동전 종류와 목표 금액 M(최대 100000)이 주어질 때, 한 번의 동작에서 각 종류의 동전을 최대 하나씩 내보낼 수 있다는 조건에서 목표 금액을 만드는 최소 동작 수를 구한다.
문제
음료 회사들 사이에 판촉 경쟁이 벌어지면서 각 회사는 매출을 늘리기 위해 노력해 왔다. Kola-Coqua는 그중에서도 가장 성공한 회사 중 하나로, 세상을 향한 인상적인 광고를 통해 대표 제품 Koque의 압도적인 시장 점유율을 확보했다.
이번에 Kola-Coqua는 자동판매기에 주목한다. 기계가 더 빠르게 반응할수록 고객이 더 만족할 것이라고 생각한 그들은 기계의 여러 부품을 개선했다.
특히 거스름돈을 돌려주는 새로운 장치를 개발했다. 새 장치는 한 번의 동작으로 한 종류의 동전을 하나씩만 내보낼 수 있지만, 한 번의 동작으로 여러 종류의 동전을 함께 내보낼 수 있다. 예를 들어 500엔, 100엔, 50엔, 10엔 동전이 있다고 하자. 6540엔의 거스름돈은 500엔과 10엔 동전을 내보내는 동작 네 번과 500엔 동전을 내보내는 동작 아홉 번으로 만들 수 있다. 결국 6540엔은 열세 번의 동작으로 돌려줄 수 있다. 새 장치 덕분에 고객이 더 빠르게 구매할 수 있게 되어 Kola-Coqua의 시장 점유율이 높아질 것이라고 본다.
그러나 프로젝트 리더는 "아직 최적이 아니다"라고 말한다. 그의 제안은 다음과 같다. 진짜 최적화는 동작 횟수를 최소화하는 것이다. 예를 들어 6540엔의 거스름돈은 500엔 동전 열 개, 100엔 동전 열 개, 50엔 동전 열 개, 10엔 동전 네 개로 만들어야 한다. 이렇게 하면 6540엔을 열 번의 동작으로 돌려줄 수 있다. 이 방식은 때로 엄청난 양의 동전을 내보내게 되더라도 거스름돈을 최대한 빠르게 돌려줄 수 있다.
사용할 수 있는 동전의 종류와 돌려주어야 할 거스름돈이 주어질 때, 위 제안에 따라 최소 동작 횟수를 계산하는 프로그램을 작성하시오. 자동판매기 안에는 충분한 양의 동전이 있다고 가정한다.
입력
입력은 여러 데이터 세트로 이루어진다. 각 데이터 세트는 두 줄로 주어진다. 첫째 줄에는 동전의 종류 수 N (N ≤ 10)과 만들어야 할 거스름돈 M (M ≤ 100000)이 주어진다. 둘째 줄에는 각 동전의 가치를 나타내는 N개의 정수가 주어진다.
입력은 N = M = 0인 데이터 세트로 끝난다. 이 데이터 세트는 처리하지 않는다.
출력
각 데이터 세트마다 지정된 거스름돈을 정확히 돌려주는 데 필요한 최소 동작 횟수를 한 줄에 출력한다.