백준 2805 나무 자르기 Python

🐸 문제 정보

2805번: 나무 자르기

 

🤖 알고리즘

이분탐색

 

⏱️ 풀이 시간

20.59

 

📝 풀이

간단한 조건이 추가된 이분탐색 문제였다.

크게 어려운 것 같진 않았는데 여전히 어느 상황에서 start와 end 값을 뭘로 바꾸어야하는지 헷갈린다.

 

사실 나무 길이를 구하는 과정 때문에 시간초과가 당연히 날거라고 생각했는데 이게 안나네...?

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

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

start, end = 0, max(heights)
while start <= end:
    mid = (start + end) // 2
    having = 0
    for height in heights:
        if height > mid: having += height - mid
    if having < m:
        end = mid - 1
    else:
        start = mid + 1

print(end)