용수 상한선
문제
한 관개 조합은 올해 농가에 나눠 줄 수 있는 물의 총량이 M으로 정해져 있다. 조합에 속한 농가는 N곳이고, 농가마다 올해 필요한 물의 양을 미리 신청해 두었다.
조합은 상한선을 하나 정해서 다음과 같이 물을 배분한다. 신청한 양이 상한선보다 작거나 같은 농가는 신청한 양을 그대로 받는다. 신청한 양이 상한선보다 큰 농가는 상한선만큼만 받는다. 상한선은 자연수로 정하며, 모든 농가에 같은 상한선을 적용한다.
배분한 물의 총량은 조합이 가진 M을 넘을 수 없다. 조합은 농가에 물을 되도록 많이 주고 싶으므로, 총량이 M을 넘지 않는 범위에서 상한선을 가장 크게 잡으려고 한다. 다만 상한선을 신청량의 최댓값보다 더 올려도 배분 결과는 달라지지 않으므로, 모든 농가에 신청한 양을 그대로 줄 수 있는 경우에는 신청량 가운데 가장 큰 값을 답으로 한다.
농가마다 신청한 물의 양과 총 공급량 M이 주어졌을 때, 배분할 수 있는 상한선의 최댓값을 구하는 프로그램을 작성하여라.
예를 들어 N=4곳의 농가가 신청한 물의 양이 다음의 표와 같고, 총 공급량 M이 485라고 해보자.
| 농가 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 신청한 양 | 120 | 110 | 140 | 150 |
상한선을 127로 잡으면 1번과 2번 농가는 신청한 양이 상한선보다 작으므로 신청한 양을 그대로 받고, 3번과 4번 농가는 상한선인 127씩 받는다. 배분한 총량은 484이므로 485를 넘지 않는다. 상한선을 128로 한 칸 올리면 총량이 486이 되어 485를 넘는다.
| 상한선 | 1번 | 2번 | 3번 | 4번 | 배분한 총량 |
|---|---|---|---|---|---|
| 127 | 120 | 110 | 127 | 127 | 484 |
| 128 | 120 | 110 | 128 | 128 | 486 |
따라서 현재 예시에서 정답은 127이다.
신청량을 모두 더한 값이 M보다 작거나 같은 경우도 있다. 그런 경우에는 모든 농가가 신청한 양을 그대로 받으므로 신청량 가운데 가장 큰 값이 답이 된다.
입출력 예시
예시 1
입력
4 120 110 140 150 485
출력
127
예시 2
입력
5 70 80 30 40 100 450
출력
100
예시 3
입력
1 264 324
출력
264
입력 조건
가장 먼저 농가의 수 N이 첫째 줄에 주어진다. N은 1 이상 10,000 이하의 자연수다.
이어서 둘째 줄에 각 농가가 신청한 물의 양이 1번 농가부터 N번 농가까지 차례대로 공백 하나로 구분되어 주어진다. 각 신청량은 1 이상 100,000 이하의 자연수다.
이어서 셋째 줄에 총 공급량 M이 주어진다. M은 1 이상 2,000,000,000 이하의 자연수다.
출력 조건
배분할 수 있는 상한선의 최댓값을 첫째 줄에 출력한다.
수 하나를 출력하고 줄을 바꾼다. 앞뒤에 다른 글자나 공백은 붙이지 않는다.
요구사항
- 입력은 표준 입력으로 받고 답은 표준 출력으로 내보냅니다
- 상한선은 자연수이며, 모든 농가에 같은 상한선을 적용합니다
- 신청한 양이 상한선보다 작거나 같은 농가는 신청한 양을 그대로 받습니다
- 모든 농가에 신청한 양을 그대로 줄 수 있으면 신청량 가운데 가장 큰 값을 출력합니다
- 입력은 세 줄입니다. 첫째 줄에 N, 둘째 줄에 신청량 N개, 셋째 줄에 M이 옵니다
- 출력은 수 하나와 줄바꿈뿐입니다
- 채점은 출력을 기대값과 글자 하나까지 견줍니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 케이스는 16개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 16개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 16개를 전부 통과해야 해결입니다.
1 264 324
264
4 120 110 140 150 485
127
5 70 80 30 40 100 450
100
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.