백준 2805 Python

• 이분 탐색을 통해 문제를 풀었을 때, 5% 부분에서 틀렸습니다와 시간초과과 발생했다.
• 5% 부분의 경우 직접 문제의 테스트 케이스 데이터를 찾아 확인해본 결과, 인덱스 범위가 넘어가면서 발생하는 문제였다. 그래서 문제 조건에서는 분명 N개만큼의 나무 정보가 들어온다고 했는데, 실제로는 N개 이상의 데이터가 들어오는 것을 확인했다. 그래서 len 함수를 통해 반복문을 돌려 해결했다.
• 시간초과의 경우 17~19번째 라인이 없다면 Pypy로 통과되나, Python3에서는 계속 시간초과가 발생했다. 이를 해결하기 위해 나무를 잘라 합을 구하던 중에 이미 목표치를 초과해버리면 그 뒤에 있는 나무들을 탐색하지 않도록하니 해결되었다.
• 처음 5% 부분에서 틀렸을 때, 구글링을 통해 찾은 모든 반례를 찾아 돌려도 전부다 맞아 많이 당황했다... 그래서 직접 테스트 케이스를 찾았는데, 이것도 나름 좋은 경험이 되었다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
LINE = list(map(int, input().split()))
low = 0  # 문제의 최소 조건 -> 길이가 1인 1개의 나무에서 1만큼의 나무를 베어야 할 때
high = max(LINE)
answer = 0

while low <= high:
    total = 0
    middle = (low + high) // 2
    for i in range(len(LINE)):
        rest = LINE[i] - middle
        if rest > 0:
            total += rest
            # 중간이 전부 탐색하기 전에 목표치를 채웠으면 멈춰야 한다.
            if total > M:
                break

    # 나무를 덜 잘라야한다.
    if total >= M:
        answer = middle
        low = middle + 1
    # 나무를 더 잘라야 한다.
    if total < M:
        high = middle - 1

print(answer)