나무 자르기
실버 III의견: 0
목재상이 나무를 베어 정확히 \(M\)미터 이상의 목재를 얻으려 한다. 절단기는 높이 \(H\)로 설정되어, \(H\)보다 높은 나무는 \(H\) 위쪽 부분이 잘려 나가고, \(H\) 이하인 나무는 그대로 둔다. 예를 들어 높이가 \(20, 15, 10, 17\) 인 나무를 \(H = 15\) 로 자르면 각각 \(5, 0, 0, 2\) 만큼의 목재를 얻어 총 \(7\)미터이다.
\(M\)미터 이상의 목재를 얻으면서 절단기 높이 \(H\)를 최대로 하고 싶다. 가능한 \(H\)의 최댓값을 출력하여라.
- \(1 \le N \le 100\,000\)
- \(1 \le M \le 2\,000\,000\,000\)
- 각 나무의 높이는 \(1\) 이상 \(1\,000\,000\,000\) 이하
- 항상 \(M\)미터를 얻을 수 있는 입력만 주어진다
첫째 줄에 나무의 수 \(N\)과 필요한 목재 길이 \(M\)이 공백으로 구분되어 주어진다.
둘째 줄에 \(N\)개의 나무 높이가 공백으로 구분되어 주어진다.
조건을 만족하는 절단기 높이의 최댓값을 한 줄에 출력한다.
4 7
20 15 10 1715H=15로 자르면 5+0+0+2=7미터를 얻을 수 있고, 이보다 높이면 7미터를 채울 수 없다.
5 20
4 42 40 26 4636H=36일 때 6+4+0+0+10=20미터로 정확히 채워지며 H의 최댓값이다.
실버 II막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
나무 자르기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
나무 자르기