Baekjoon 문제 풀기 (2805번 : 나무 자르기) Python

2805번 : 나무 자르기

1. 문제읽기

---

잘랐을 때 나무 길이가 m과 같거나 큰 절단기의 높이의 최댓값 구하기

일단 입력값이 말도안되게 크기 때문에 이진탐색 알고리즘을 써야한다는 것을 눈치챘다.
예제 두개를 직접 계산해보니 이해가 쉬웠다.
절단기 높이보다 작으면 자르지 않고, 크면 자른 후 자른 나무의 길이를 다 더해서 m보다 크거나 같으면 된다.

2. 제출 코드

---

나는 아래와 같이 코드를 작성했는데, 계속 시간초과로 실패해서 input을 readline으로도 바꿔봤지만 효과가 없었다.
pypy는 고려하지 않았다.
코드를 분석해본 결과 아래 코드는 간과한 점이 두가지 있었다.

1. while 문 안의 for문의 시간복잡도
2. mid값이 딱 떨어지지 않는 경우

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
tree = list(map(int, sys.stdin.readline().rstrip().split()))

start = 0
end = max(tree)

while 1:
    ans = 0
    mid = (start+end)//2
    for i in tree:
        if i-mid>0:
            ans += (i-mid)
    if ans > m:
        start = mid+1
    elif ans < m:
        end = mid-1
    else:
        print(mid)
        break

3. 공부할 것

---

이진탐색은 쉬운 것이라고 생각했는데, while 문에 조건을 왜 start <= end를 써주는지 이해를 못한 상태였었나보다.
내가 제출한 코드의 1번 문제점은 시간을 조금이라도 줄이기 위해 생각해본다면 찾을 수 있는 정도였다면, 2번 문제점은 바로 이 이진탐색의 종료 조건과 연결되어있다.

start <= end 일 때 반복문을 종료시켜주지 않는다면 예를 들어 입력값이 2 9 그리고 100 100 일 경우, 타겟(mid)가 9를 정확히 찾을 수가 없기 때문에 무한루프에 빠지게 된다. 결국 시간초과이지만 틀렸습니다와 같은 것이다.
나와 정확히 똑같은 상황을 질문으로 올린 분의 글을 찾지 못했다면 계속 고민에 빠져있었을 것이다.
2 9 100 100 이 입력값인 경우, mid가 95일 때 ans는 10으로, mid가 96일 때 ans는 8으로 9인 경우를 찾지 못한다.
이 때 문제는 높이의 최댓값이므로 start <= end 조건을 걸어 ans를 정확히 찾지 못했을 경우 가장 큰 경우인 95를 출력해야한다.

정답 코드

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
tree = list(map(int, sys.stdin.readline().rstrip().split()))

start = 0
end = max(tree)

while start <= end:
    ans = 0
    mid = (start+end)//2
    for i in tree:
        if i-mid>0:
            ans += (i-mid)
            if ans > m:
                break

    if ans >= m:
        start = mid+1
    elif ans < m:
        end = mid-1

print(end)