[백준] 2805 - 나무 자르기

문제 링크

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

문제 요약

상근이는 M미터의 나무가 필요하고, 이를 위해 주어진 나무들을 절단기로 자를 높이 H를 찾아야 합니다. 절단기의 높이를 설정하면, 나무 중에서 H보다 큰 나무는 그 위의 부분이 잘리고, H보다 작은 나무는 자르지 않습니다. 절단 후 나무 길이의 합이 M미터 이상이 되도록 하는 절단기의 높이 H의 최댓값을 구하는 것이 목표입니다.

조건 요약

• 나무의 수 N은 최대 1,000,000개.
• 상근이가 가져가려는 나무의 길이 M은 최대 2,000,000,000.
• 나무의 높이는 최대 1,000,000,000.
• 설정할 수 있는 절단기의 높이 H는 정수 또는 0이며, H가 클수록 더 많은 부분의 나무가 잘리게 됩니다.

푼 방법

1. 이분 탐색의 범위 설정: 절단기의 높이를 min = 1, max = 나무 중 가장 높은 값으로 설정합니다.
2. 이분 탐색 반복: 절단기의 높이 avg를 설정하고, 이 높이로 잘린 나무의 길이를 계산합니다.
3. 조건에 따른 범위 조정:
   • 잘린 나무의 길이가 m 이상이면 절단기 높이를 더 높여서 탐색.
   • 잘린 나무의 길이가 m 미만이면 절단기 높이를 낮춰서 탐색.
4. 최종 결과 출력: 이분 탐색이 끝나면 max 값이 최적의 절단기 높이가 됩니다.

정답 코드

n, m = list(map(int, input().split()))
woods = list(map(int, input().split()))

max=max(woods)
min=1
while min<=max:
    avg=(max+min)//2
    sum=0
    for i in woods:
        if i-avg>0:
            sum+=i-avg
    if sum>=m:
        min=avg+1
    else:
        max=avg-1
print(max)