[백준] 2805 - 나무 자르기 [Python(파이썬)]

문제

www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

풀이

이진탐색 문제였다. N의 범위가 크기 때문에 O(N^2)의 풀이로는 시간초과가 날 수 밖에 없다.

절단한 나무 길이의 합(_sum)을 집으로 가져가야 하는 나무의 길이(M)와 비교하여 포인터를 옮긴다.

 

이때, 합이 길이보다 작다면 right포인터를 mid-1로 줄여서 탐색의 범위를 줄인다.

반대로 크다면 left포인터를 mid+1로 옮긴 후, 현재 mid포인터가 가리키고 있는 값을 결과에 저장한다.

 

이와 같은 작업을 반복하여 최댓값을 구할 수 있다.

 

코드

import sys

def get_height():
    result = 0
    left, right = 0, MAX-1
    while left <= right: # 이진탐색
        mid = (left+right)
        _sum = get_sum(mid)
        if _sum < m:
            right = mid - 1
        elif _sum >= m:
            left = mid + 1
            result = mid
    return result

def get_sum(h):
    _sum = 0
    for tree in trees:
        diff = tree - h
        if diff > 0:
            _sum += diff
    return _sum

n, m = map(int, sys.stdin.readline().split())
trees = [int(x) for x in sys.stdin.readline().split()]

result = 0
MAX = max(trees)
print(get_height())