[백준] 2805번 나무 자르기

<문제>

 

 

 

 

<입력/ 출력>

 

 

<1트>

import sys

n,m = map(int, sys.stdin.readline().split())
array = list(map(int, sys.stdin.readline().split()))
start = 0
end = max(array)

while start <= end:
    result = 0
    mid = (start + end)//2
    for i in array:
        if i - mid > 0:
            result += i - mid
    if result < m:       # 필요한 길이보다 result가 작으므로, 잘린 나무가 더 길어져야 한다.
        end = mid - 1
    else:
        start = mid + 1

print(end)

입출력은 동일했으나, 시간초과 결과가 나왔다.

 

 

<성공>

import sys
n,m = map(int, sys.stdin.readline().split())
array = list(map(int, sys.stdin.readline().split()))
start, end = 0, max(array)

while start <= end:
    result = 0
    mid = (start + end)//2
    for i in array:
        if i > mid:
            result += i - mid
    if result >= m:
        start = mid + 1
    else:
        end = mid - 1

print(end)

더 이상 어디서 시간을 줄일 수 있는지 모르겠어서, 인터넷 검색을 통해 코드를 비교해보았다.

일단, if i - mid > 0 에서 if i > mid로 바꾸어 주었고,

if result < m에서 if result >= m으로 비교문을 바꾸어주었더니 성공하였다.

왜 시간 차이가 나는지 잘 이해되지 않는다.

 

 

 

 

 

 

<결과>