소금 거두기
문제
한 염전은 구획이 N개로 나뉘어 있고, 구획마다 소금이 쌓여 있다. 쌓인 높이는 구획마다 정해져 있으며, 두 구획의 높이가 같을 수도 있다.
소금을 거둘 때는 밀대를 쓴다. 밀대의 높이를 H로 맞추고 염전을 한 번 밀면, 쌓인 높이가 H보다 높은 구획에서는 H를 넘는 부분만 깎여 나오고 나머지는 그 자리에 남는다. 쌓인 높이가 H와 같거나 H보다 낮은 구획에서는 아무것도 나오지 않는다. 그래서 어떤 구획에서 나오는 소금의 양은 그 구획에 쌓인 높이에서 H를 뺀 값이고, 그 값이 0보다 작으면 아무것도 나오지 않는다. 밀대는 한 번만 밀며 모든 구획을 같은 높이로 민다.
올해 넘겨야 하는 소금의 양이 M으로 정해져 있다. 거둔 양이 M보다 적으면 안 되므로 밀대를 낮게 맞추어야 하지만, 염전에는 소금을 되도록 많이 남기고 싶으므로 밀대는 되도록 높게 맞추려고 한다. 밀대의 높이는 0 이상의 정수로 맞춘다.
구획마다 쌓인 소금의 높이와 넘겨야 하는 양 M이 주어졌을 때, 거둔 양이 M보다 적지 않게 하는 밀대 높이의 최댓값을 구하는 프로그램을 작성하여라.
예를 들어 N=4개의 구획에 쌓인 소금의 높이가 다음의 표와 같고, 넘겨야 하는 양 M이 7이라고 해보자.
| 구획 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 쌓인 높이 | 20 | 15 | 10 | 17 |
밀대를 15로 맞추면 1번 구획에서 5가 나오고 4번 구획에서 2가 나온다. 2번 구획은 쌓인 높이가 밀대와 같고 3번 구획은 밀대보다 낮으므로 아무것도 나오지 않는다. 거둔 양은 7이므로 넘겨야 하는 7보다 적지 않다. 밀대를 16으로 한 칸 올리면 거둔 양이 5가 되어 7보다 적어진다.
| 밀대 높이 | 1번 | 2번 | 3번 | 4번 | 거둔 양 |
|---|---|---|---|---|---|
| 15 | 5 | 0 | 0 | 2 | 7 |
| 16 | 4 | 0 | 0 | 1 | 5 |
따라서 현재 예시에서 정답은 15다. 밀대를 낮출수록 거두는 양은 늘어나므로, 거둔 양이 M보다 적지 않은 높이 가운데 가장 높은 것을 찾으면 된다.
입출력 예시
예시 1
입력
4 7 20 15 10 17
출력
15
예시 2
입력
5 20 4 42 40 26 46
출력
36
예시 3
입력
1 444 917
출력
473
입력 조건
가장 먼저 구획의 수 N과 넘겨야 하는 소금의 양 M이 첫째 줄에 공백 하나로 구분되어 차례대로 주어진다. N은 1 이상 1,000,000 이하의 자연수이고, M은 1 이상의 자연수이며 모든 구획에 쌓인 높이의 합보다 크지 않다.
이어서 둘째 줄에 각 구획에 쌓인 소금의 높이가 1번 구획부터 N번 구획까지 차례대로 공백 하나로 구분되어 주어진다. 각 높이는 1 이상 1,000,000,000 이하의 자연수다.
출력 조건
거둔 양이 M보다 적지 않게 하는 밀대 높이의 최댓값을 첫째 줄에 출력한다.
수 하나를 출력하고 줄을 바꾼다. 앞뒤에 다른 글자나 공백은 붙이지 않는다.
요구사항
- 입력은 표준 입력으로 받고 답은 표준 출력으로 내보냅니다
- 밀대는 한 번만 밀며 모든 구획을 같은 높이로 밉니다
- 쌓인 높이가 밀대 높이보다 높은 구획에서만 소금이 나오고, 나오는 양은 그 차이만큼입니다
- 거둔 양이 M보다 적지 않아야 하며, 그 가운데 밀대 높이를 가장 크게 잡습니다
- 거둔 양의 합은 1,000,000,000보다 훨씬 커질 수 있으므로, 더하는 과정에서 수가 넘치지 않는지 보십시오
- N이 1,000,000까지 올라가므로 밀대 높이를 0부터 하나씩 올려 보는 방법으로는 시간 안에 끝나지 않습니다
- 채점은 출력을 기대값과 글자 하나까지 견줍니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 케이스는 16개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 16개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 16개를 전부 통과해야 해결입니다.
1 444 917
473
4 7 20 15 10 17
15
5 20 4 42 40 26 46
36
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.