[백준 2024/09/10] 2805번 나무 자르기

1. 문제

https://www.acmicpc.net/problem/2805

 

2. 접근 방법

처음엔, tree 높이를 sort() 한 후, 높이에 따른 잘라지는 나무의 높이를 알아내고, 

해당 높이가 원하는 높이보다 작을 시, 잘라지는 높이에 따른 4*x, 3*x, ... 을 해주려고 했고, 

코드를 작성하기도 하였다.

def get_max_h(n, wanted_height, trees):
    for i in range(n):
        left = 0
        for j in range(i+1, n, 1):
            left += trees[j] - trees[i]
        if left <= wanted:
            #print("i:", i)
            #print("left:", left)
            return i, left


if __name__ == "__main__":
    n, wanted = map(int, input().split())
    trees = list(map(int, input().split()))
    trees.sort()
    i, left = get_max_h(n, wanted, trees)
    print(trees[i] - ((wanted-left)//(n - i)))

 

해당 방법이 상당히 괜찮다고 개인적으로 생각하였지만, O(n^2)의 한계로 시간 초과 통과를 하지 못하였다.

 

이에, binary search로 접근 해야 함을 깨닫고, 해당 코드를 작성하였다.

처음에 best_h를 변경시키는 부분을 어디에 넣어주어야 하나 고민을 하기도 하였다.

하지만, 당연하게도, gotten_trees(mid, trees) = wanted_trees가 해당되는 if else 문에 넣어주어야 한다.\

따라서, else 문 아래에 best_h를 update 하는 코드를 작성해 주었다.

 

3. 코드

def gotten_trees(h, trees):
    got = 0
    for t in trees:
        if (t - h) > 0:
            got += (t - h)

    return got


def get_max_h(n, wanted_trees, trees):
    trees.sort()
    l = 0
    r = trees[-1]
    best_h = 0
    while l <= r:
        mid = (l + r) // 2
        if gotten_trees(mid, trees) < wanted_trees:
            r = mid - 1
        else:
            best_h = mid
            l = mid + 1

    return best_h


if __name__ == "__main__":
    n, wanted = map(int, input().split())
    trees = list(map(int, input().split()))
    print(get_max_h(n, wanted, trees))