[백준 2805] 나무 자르기

🍎 [백준 2805] 나무 자르기

문제링크

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

 

⚾ 코드(pypy3)

import sys
input = sys.stdin.readline

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

tree = list(map(int, input().split()))

end = max(tree)
start = 0

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

    remain = 0

    for i in tree:
        if i > mid:
            remain += i-mid

    if remain < m:
        end = mid-1
    else:
        start = mid+1


print(end)

 

🔔 해결 과정 & 깨달은 점

- 해당 문제는 전형적인 이진탐색 문제이다.

- 입력 값이 20억이므로 이진 탐색을 시도해보자.

- 처음에 cm가 아닌, 인덱스의 중앙값으로 시도를 해보려고 해서 문제가 잘 풀리지 않았다. cm는 각 나무의 길이 만큼 잘리는 게 아니기 때문에 cm로 접근 할 필요가 있다.