사과 담는 바구니

200점케이스 15출제 dongbinna

10월 30일에 올라온 문제입니다.

문제

어느 과수원에서는 수확한 사과를 바구니에 담아 내보낸다. 과수원에는 크기가 N가지인 바구니가 있고, 각 크기의 바구니에는 정해진 개수의 사과만 담는다. 모자라게 담거나 넘치게 담는 일은 없다. 바구니는 크기마다 넉넉하게 있어서 같은 크기를 몇 개든 쓸 수 있다.

오늘은 사과를 정확히 K개 내보내야 한다. 바구니를 몇 개 골라 담은 사과의 개수를 모두 더했을 때 그 값이 정확히 K가 되어야 한다. 이때 쓰는 바구니의 개수를 가장 적게 하려고 한다.

예를 들어 N=10가지 바구니가 다음의 표와 같고, 내보낼 사과가 K=4,790개라고 해보자.

바구니	1	2	3	4	5	6	7	8	9	10
담는 사과 수	1	5	10	50	100	500	1000	5000	10000	50000

많이 담는 바구니부터 쓸 수 있는 만큼 쓰면 다음과 같다. 50,000개와 10,000개와 5,000개를 담는 바구니는 4,790개보다 많이 담으므로 한 개도 쓸 수 없다.

담는 사과 수	1000	500	100	50	10	5	1
쓴 바구니 수	4	1	2	1	4	0	0
남은 사과 수	790	290	90	40	0	0	0

쓴 바구니를 모두 더하면 4 + 1 + 2 + 1 + 4 = 12개다. 이보다 적게 쓰는 방법은 없으므로 이 경우의 답은 12다.

많이 담는 바구니부터 쓰는 것이 왜 최선인지 살펴보자. 위 예시에서 1,000개를 담는 바구니를 네 개 쓰는 대신 세 개만 쓰고 남은 사과를 작은 바구니로 채우면 다음과 같다.

1,000개 바구니를 쓴 수	남은 사과를 담은 바구니 수	전체 바구니 수
4개	8개	12개
3개	10개	13개

1,000개 바구니를 하나 덜 쓰면 사과 1,000개를 더 작은 바구니로 채워야 하므로 바구니가 오히려 늘어난다. 바구니가 담는 사과의 개수가 서로 배수 관계이기 때문에 이런 일이 언제나 일어난다. 이 조건이 없으면 많이 담는 바구니부터 쓰는 방법이 최솟값을 주지 않는다.

바구니의 종류와 내보낼 사과의 개수가 주어졌을 때, 써야 하는 바구니 개수의 최솟값을 구하는 프로그램을 작성하여라.

입출력 예시

예시 1

입력

출력

예시 2

입력

1 11
1

출력

예시 3

입력

출력

입력 조건

가장 먼저 첫째 줄에 바구니의 종류 수 N과 내보낼 사과의 개수 K가 공백 하나로 구분되어 주어진다. N은 1 이상 10 이하의 자연수이고, K는 100,000,000보다 작거나 같은 자연수다.
이어서 N개의 줄에 걸쳐 각 바구니가 담는 사과의 개수가 한 줄에 하나씩 주어진다. 이 값은 1 이상 100,000 이하의 자연수다.
바구니가 담는 사과의 개수는 적게 담는 것부터 차례대로 주어진다. 가장 작은 바구니는 사과 1개를 담는다.
그리고 어떤 바구니가 담는 사과의 개수는 그보다 작은 바구니가 담는 사과의 개수의 배수다.

출력 조건

사과를 정확히 K개 담기 위해 써야 하는 바구니 개수의 최솟값을 첫째 줄에 출력한다.
수 하나를 출력하고 줄을 바꾼다. 앞뒤에 다른 글자나 공백은 붙이지 않는다.

요구사항

입력은 표준 입력으로 받고 답은 표준 출력으로 내보냅니다
같은 크기의 바구니를 여러 개 써도 됩니다. 한 개도 쓰지 않는 크기가 있어도 됩니다
담은 사과의 개수를 모두 더한 값이 정확히 K여야 합니다
가장 작은 바구니가 사과 1개를 담으므로 K가 무엇이든 담는 방법은 반드시 있습니다
바구니가 담는 사과의 개수가 서로 배수 관계라는 조건이 이 문제의 핵심입니다. 이 조건이 없으면 많이 담는 바구니부터 쓰는 방법이 최솟값을 주지 않습니다
채점은 출력을 기대값과 글자 하나까지 견줍니다
표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
쓸 수 있는 말은 파이썬, 자바스크립트입니다
메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
케이스 15개를 전부 통과해야 해결입니다.

문제의 요구 사항을 잘 읽고 해결해 주세요. 단, 채점 과정을 건드려 통과한 것처럼 꾸미는 경우 적발 시 제재될 수 있습니다. 제출한 코드는 순위표에 함께 공개됩니다.

예시

공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.

입력

기대 출력

1 11
1

풀이

코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.

0자1줄메모리 256MB (적어만 둡니다)기준 2.0ms

제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.

공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.

이 문제를 푼 사람

아직 없습니다. 첫 번째가 되실 수 있습니다.