[알고리즘] 백준 2805 - 나무자르기

문제

나무 자르기

접근

1. 이코테의 떡볶이 떡 자르기와 동일하다

2. 시작과 끝을 설정하고 total 변수에 배열안에 있는 나무들을 순차적으로 ( 나무 - mid ) 을 total에 넣어준다

3. total값과 m값을 비교해 start, end의 위치를 옮겨준다

 

풀이

# 나무 자르기 - 떡볶이 떡 만들기랑 비슷
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

start = 0
end = max(array)
res = 0

while start <= end:
    mid = (start+end) // 2
    total = 0  # 잘린 나무들의 크기들의 합

    # 남아있는 나무의 크기를 생각하기
    for x in array:
        if x > mid:
            total += x - mid
    if total < m:
        end = mid - 1
    else:
        res = mid
        start = mid + 1
print(res)