백준 2805 나무 자르기

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

2805번: 나무 자르기

📌 해결순서

문제에서 요구하는 값이 절단기 높이의 최댓값이므로 조건을 만족하는 절단기의 높이를 작은값부터 최댓값이 될때까지 키워나가면 된다.

절단기의 높이가 높아질수록 상근이가 가져갈수 있는 나무는 적어진다

start = 0 / end = max(lst)

 

1. 절단기의 높이가 너무 짧은 경우

-> 이 경우에는 상근이가 가져가려는 나무의 길이보다 더 많은 나무가 잘리므로 현재 절단기의 높이보다 더 짧은 경우에 대해서 탐색하지 않는다.

따라서, start = mid + 1 로 설정

2. 절단기의 높이가 너무 긴 경우

-> 이 경우에는 상근이가 가져가려는 나무의 길이보다 더 적은 나무가 잘리므로 현재 절단기의 높이보다 더 긴 경우에 대해서 탐색하지 않는다.

따라서, end = mid - 1

📌 코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n, m = map(int, input().split())
    lst = list(map(int, input().split()))

    ans = 0
    start = 0
    end = max(lst)

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

        for tree in lst:
            if tree > mid:
                length += tree - mid

        if length < m:
            end = mid - 1
        else:
            ans = mid
            start = mid + 1

    print(ans)