Python - [백준]2805-나무자르기

출처

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

문제

나무를 최대한 베지않으면서 집에 가져갈 높이가 M미터가 되도록 하는 최소한의 절단기 높이를 구하는 문제이다.

접근 방법

전형적인 이분탐색 문제이다. 시작과 끝을 0과 가장 높은 나무로 설정한 뒤에 가운데 값으로 계산한 뒤 시작점이나 끝점을 옮겨가며 해결하는 문제이다.

풀이

0과 가장 높은 나무로 start, end로 설정한 후, mid값으로 나무를 잘라냈을 때 목표치 보다 낮게 잘린다면 mid보다 아래는 볼 필요가없으므로 start를 mid+1로 초기화하여 다시 수행하고, 목표치 보다 높다면 mid 위에는 볼 필요가 없으니 end를 mid-1로 초기화하여 최적해에 근접할 때 까지 연산을 수행한다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = list(map(int, input().split()))
start, end = 0, max(arr)
max_h = 0
while start <= end:
    mid = (start + end)//2
    tmp = 0
    for i in arr:
        if i - mid > 0:
            tmp += i - mid
    if tmp < m:
        end = mid - 1
    else:
        max_h = mid
        start = mid + 1
print(max_h)