[백준 2805] 나무 자르기

문제

절단기로 한 줄에 나열되어 있는 나무를 잘라서 M미터의 나무를 구하려고 한다.

절단기는 고정이 되어있고 높이를 조절하여 해당 높이만큼 나무를 자를 수 있다.

N개의 나무 중 절단기로 잘라서 M미터의 나무를 가지려고 할 때 절단기의 최대 높이를 구하라.

 

정확히 M미터를 가져가지 못하는 경우는 없다.

 

입력

첫째 줄에 N과 M을 입력하고 이어서 N개의 나무를 입력한다.

 

출력

절단기의 최대 높이를 출력한다.

---

접근

이분탐색을 연습해보았다.

구하려고하는 것은 절단기의 최대높이이다. 따라서 절단기의 높이를 조절하여 M미터를 가져갈 수 있는지 탐색을 해야한다.

 

절단기의 높이를 나무들의 최소높이부터 최대높이까지 탐색하면서 구하기에는 오래걸린다.

따라서 절단기의 높이를 1과 나무의 최대높이의 중간값으로 시작하여 찾아간다.

 

구현

left는 1, right는 나무들의 최대높이로 초기화하고 이분탐색을 시작한다.

절단기의 높이를 mid로 하고 left와 right를 더한 값에 2로 나눈 값으로 설정한다.

total은 mid를 초과하는 나무들을 잘라서 합친 값이다.

그리고 다시 나무의 높이를 조절하고 절단기의 최대높이를 구하기 위해 total이 M이상일 때 최댓값 비교를 진행한다.

 

여기서 total을 for문으로 하면 시간초과가 발생하고 컴프리헨션으로 하면 시간초과가 발생하지 않는다.

import sys
input = sys.stdin.readline

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

left = 1
right = max(tree_list)
answer = 0
while left<=right:
    mid = (left+right)//2
    total = sum([tree-mid if tree>mid else 0 for tree in tree_list])
    if total >= M:
        left = mid + 1
        if answer < mid:
            answer = mid
    else:
        right = mid - 1

print(answer)