boj2805-나무자르기

문제 : 나무자르기

parametric search로 해결 .

• 시간초과 풀이

import sys

if __name__ == '__main__':
    input = sys.stdin.readline

    N,M = map(int, input().split())
    height = sorted(list(map(int, input().split())))

    start = 0
    end = max(height)
    result = 0

    while start <= end:
        total = 0
        mid = (start+end) // 2
        for h in height:
            if h-mid > 0:
                total += (h - mid) 
        # print(f'start : {start}, end : {end}, mid : {mid}, total : {total}')
        if total >= M:
            result = mid
            start = mid + 1
        else:
            end = mid - 1
        # print(f'result : {result}')

    print(result)

• 맞은 풀이

import sys

if __name__ == '__main__':
    input = sys.stdin.readline

    N,M = map(int, input().split())
    height = list(map(int, input().split()))

    start = 0
    end = max(height)
    result = 0

    while start <= end:
        total = 0
        mid = (start+end) // 2
        total = sum(h-mid if h > mid else 0 for h in height)
        # print(f'start : {start}, end : {end}, mid : {mid}, total : {total}')
        if total == M:
            result = mid
            break
        elif total > M:
            result = mid
            start = mid + 1
        else:
            end = mid - 1
        # print(f'result : {result}')

    print(result)

total 과 M비교 부분은 바꿔도 그대로 시간초과였고,
total = sum(h-mid if h > mid else 0 for h in height) 로 바꾸니까 정답
왜지 ?.. 삽입 연산을 한번만 해서인가?