[python] 백준 2805번 나무 자르기

백준 2805번 나무 자르기

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

문제

풀이

이것이 취업을 위한 코딩테스트다에서 떡볶이 떡 만들기 와 동일.
저 입력값이 너무 크면 이진탐색을 생각해볼 것

대상 데이터가 1이라면

# 이진탐색
import sys 
input = sys.stdin.readline
n, m = map(int, input().split())
treelist = list(map(int, input().split()))

# 처음과 끝
start = 0
end = max(treelist)
result = 0

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

    for i in treelist:
        if i > mid:
            total += i - mid

    if total < m:
        end = mid - 1 
    # total >= m 인 경우, result 업데이트
    else:
        result = mid 
        start = mid + 1

print(result)

📌 주의

• 원하는 값보다 mid 값이 더 크면 end 를 mid - 1 로, 원하는 값보다 mid 값이 더 작으면 start 를 mid + 1 로.