백준, 나무 자르기, 2805

[유형]

이분탐색

 

[문제링크]

https://www.acmicpc.net/problem/2805

 

[요약]

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다.

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

 

[문제풀이]

mid: 임의의 절단기 높이

cnt: 집에 가져갈 나무의 길이의 합

cnt >= M: 집에 가져가려고 했던 길이보다 긴 경우, 절단기의 높이를 높이고

반대의 경우에는 절단기의 높이를 낮춘다.

import sys
from collections import Counter
def input():
    return sys.stdin.readline().rstrip()

N, M = map(int, input().split())
trees = list(map(int, input().split()))

start = 1
end = max(trees)

while start <= end:
    cnt = 0
    mid = (start + end) // 2

    for tree in trees:
        if tree >= mid:
            cnt += tree-mid
            if cnt >= M:
                break

    if cnt >= M:
        start = mid+1
    else:
        end = mid-1
print(end)