[파이썬, Python] 백준 2805: 나무 자르기

문제

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

2805번: 나무 자르기

코드

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
tree = list(map(int, input().split()))
start, end = 0, max(tree)

while start <= end:
    mid = (start+end)//2
    cut_tree = 0
    for i in tree:
        if i >= mid:
            cut_tree += i - mid
    if cut_tree >= m:
        start = mid + 1
    else: end = mid - 1
print(end)

설명

우선 나무의 길이를 입력하고 시작과 끝점을 정해준다.
시작은 0, 끝은 가장 긴 나무의 길이로 선택한다.

start가 end보다 작을 동안 루프를 돌려준다.
mid를 둘의 중간지점으로 정해주고, 잘라야 할 나무의 길이를 표시할 함수를 하나 만들어준다.

만약 나무의 길이가 설정한 길이(mid)보다 길다면 나무를 자르게 되므로,
자른 나무의 길이(cut_tree)에 더해준다.

만약 자른 나무의 길이가 가져가야할 나무의 길이보다 길다면,
절단기의 높이를 더 높여도 될 가능성이 있으므로 start 지점을 mid보다 1 높은 수로 설정하고 다시 반복문을 돌려준다.

반대의 경우(가져가야할 나무의 길이보다 짧다면)는
절단기의 높이를 더 낮춰야 하므로 end 지점을 mid보다 1 낮은 수로 설정하고 다시 반복한다.

반복문이 종료됐을 때, end를 출력해서 최댓값을 표시한다.