농부 존은 Q( 1 <= Q <= 20,000) 만큼의 우유를 통하나에 담아서 고객에게 전달해야 한다.
존은 절약 정신이 투철해서 가게에서 그는 Q 쿼터를 만들기위해 필요한 통을 구입하려고 한다.
통의 가격은 같기 때문에 Q 쿼터의 통을 채우기위해 가장 통의 수를 최소로 하여 구입하고 자 한다.
더불어 , 최소의 조합이 두 개 이상 존재한다면 아래와 같은 방법으로 선택한다.
즉 통들을 오름차순 정열해서 각 직합의 첫번째 통을 비교해서 그 중 작은 것을 선택 한다. 만약 첫 번째 통이 같다면 다음 통을 .... 이런식으로 다른 것이 나타날 때 더 작은 것을 선택한다.그러므로 3,5,7,10 과 3,6,7,8 둘 중에서 3,5,7,10 에 선택된다.
통에 있는 우유를 완전히 사용 해야지 버리거나 다른 통에 담을 수는 없다.
만약 1 쿼터짜리 통을 가지고 있다면 존은 이 통만 있으면 다른 통을 사용할 필요가 없다.
구입해야 할 최소 통을 개수를 구하라. 단, 문제에서 주어지는 데이터는 최소 한 가지이상의 답이 있다고 가정한다.
입력 16 3 3 5 7 출력 2 3 5
출처: usaco