[백준] 2805번 나무 자르기

💡문제접근

• 전체적인 코드는 작성하는 과정에서 문제가 없었지만 반례가 존재하여 코드를 거듭 수정했다.
• 나무의 수 N의 범위는 1 ≤ N ≤ 1,000,000이고 가져가고자 하는 나무의 길이 M의 범위는 1 ≤ M ≤ 2,000,000,000이다. 선형탐색으로 절대 풀 수 없는 범위에 시간도 안될 것 같아서 이분 탐색으로 코드를 작성했다.

💡코드(메모리 : 149704KB, 시간 : 2220ms)

import sys
input = sys.stdin.readline

def binary_search(target, data):
    start = 1
    end = max(data)
    while True:
        val = 0
        if start > end:
            break
        mid = (start + end) // 2
        for i in data:
            if i >= mid:
                val += (i - mid)
        if val >= target:
            start = mid + 1
        else:
            end = mid - 1
    return end

N, M = map(int, input().strip().split())
tree_height = list(map(int, input().strip().split()))
print(binary_search(M, tree_height))

💡소요시간 : 10m