[백준] 2805번 나무 자르기 파이썬 풀이

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

2805번: 나무 자르기

---

1. 접근 방식

• 무언가를 자르고, 최대값을 구하는 문제이므로 이진 탐색으로 접근하자.

실제로 그냥 반복문으로 값을 하나씩 줄이거나 늘리는 방식으로 코드를 작성하면 시간 초과가 난다. 빠르게 최대값을 탐색하기 위해 이진 탐색을 해야 한다.

 

• 이진 탐색을 위한 시작 값과 끝 값을 설정하자.

끝 값은 당연히 입력 받은 나무 길이 중 가장 긴 나무 길이로 설정한다. 시작 값은 조금 고민이 됐는데, 처음에는 입력 받은 나무 길이 중 가장 짧은 나무 길이로 설정했었다. 그러나 이대로는 제대로 된 처리가 불가능하다. 왜냐하면 문제에서 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이라고 했기 때문이다.

시작 값을 최소 나무 길이로 설정하면 절대 절단기 높이가 0이 될 수 없다. 실제로 질문 게시글 댓글에 달린 아래 데이터를 입력하면 0이 아니라, 다른 값이 출력된다.

2 10
5 5

따라서 시작 값은 절단기의 최소 높이인 0으로 설정해야 한다.

 

다음 그림은 아래 데이터를 입력할 때의 이진 탐색 과정을 보여준다. m = 4일 때이다.

4 4
20 15 10 17

이진 탐색: left - mid - right

 

 

 

2. 정답 코드

import sys

input = sys.stdin.readline

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

left, right = 0, max(trees)

while left <= right:
    mid = (left + right) // 2

    length = sum([t - mid for t in trees if t > mid])

    if length < m:
        right = mid - 1

    else:
        left = mid + 1

print(right)