글 읽기 - 이분탐색으로 했는데 시간초과가 납니다. 반례부탁드립니다.

chsun0303 6년 전 0

어디서 무한루프 도는게 있는건지 반례부탁드립니다.

무한루프 도는 부분이 없다면 어떻게 개선할 수 있을까요?

감사합니다.

import sys


n, l = map(int, sys.stdin.readline().strip().split(" "))
t = list(map(int, sys.stdin.readline().strip().split(" ")))

low = 0
high = max(t)
pos = max(t) // 2

while True:
    curr_len = 0 # 현재 얻을 수 있는 나무 길이

    for i in range(n):
        if t[i] - pos >= 0:
            curr_len += (t[i] - pos) # 현재 위치(pos)에서 잘랐을 때 나무 길이(curr_len) 구함

    if curr_len == l or pos == max(t) - 1 or pos == 1: # 현재 나무 길이(curr_len) == l 이거나,
        break                                          # pos == 1 혹은 pos == 가장 큰 나무의 길이 - 1 일 때 break
    elif curr_len > l:
        low = pos
        pos = (pos + high) // 2
    elif curr_len < l:
        high = pos
        pos = (low + pos) // 2

print(pos)