[백준 2024/02/25] 2805번 나무 자르기

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

2805번: 나무 자르기

 

1. 접근 방법

이 문제의 경우 2 방법으로 접근하였다.

 

첫 번째 방법)

최대 height를 나무들 중에서 제일 높은 나무로 정한다.

 

이후, height -= 1을 해가면서 적정한 height를 찾는다.

하지만, 이런식으로만 구성을 하게 되면 시간 초과가 나게 된다.

 

만약 현재 height에서 구한 남은 나무의 길이와 m의 차이가 현재 남아 있는 나무의 개수의 배수일 때 -1 이 아니라, 배수에 맞게끔 -를 해주었다.

 

즉, 20, 15, 10, 17의 나무 길이에서 height를 19로 설정했다고 가정해보자. 그리고 가져가려고 하는 나무의 길이를 7로 정했다.

 

-> 19로 자르게 되면 1의 나무 길이가 남게 된다.

구해야 하는 나무 길이 7 에서 1을 빼게 되면 6이 남는다.

 

현재 4개의 나무 그루가 있기 때문에 18로 잘랐을 때, 모든 나무가 18보다 커서 잘라진다고 가정을 하면, 최대 4의 길이만큼 더 자를 수 있다. 

하지만 현재 6을 더 구해야 하므로, height -= 1을 해서 잘라도 7개의 나무 길이를 채울 수 없다. 

 

minus = (m - sum_tree)//num_tree + 1

를 통해서, 4의 배수에 맞게끔 height -= minus 를 해주었다.

현재 경우의 경우 (7 - 1)//4 + 1 => 2가 되어, 19 - 2 인 17로 다음 나무를 잘라볼 것이다.

 

이렇게 불필요한 height에 따른 계산을 피해주어 효율적으로 값을 구하고자 하였다.

 

두 번째 방법)

두 번째 방법은 전형적인 binary search를 사용해 주었다.

 

while min_height <= max_height:

 

작거나 같아도, while문을 계속 진행하며, 어긋났을 때, 멈추게 된다. 

 

2. 코드

def cal(trees, height, num_tree, m):
    while True:
        sum_tree = 0

        for tree in trees:
            cut = tree - height
            if cut <= 0:
                break
            sum_tree += cut

        if sum_tree >= m:
            return height
        minus = (m - sum_tree)//num_tree + 1
        if minus < 1:
            minus = 1
        height -= minus


def main():
    num_tree, m = map(int, input().split())
    trees = list(map(int, input().split()))
    trees.sort(reverse=True)
    height = trees[0]

    start_point = m // len(trees)
    print(cal(trees, height - start_point, num_tree, m))


if __name__ == "__main__":
    main()

def m_height(m, trees):
    min_height = 0
    max_height = max(trees)

    while min_height <= max_height:

        cut = (min_height + max_height) // 2
        total = 0
        for tree in trees:
            leftover = tree - cut
            if leftover > 0:
                total += leftover

        if total >= m:
            min_height = cut + 1
        else:
            max_height = cut - 1

    return max_height


def main():
    num_tree, m = map(int, input().split())
    trees = list(map(int, input().split()))
    print(m_height(m, trees))


if __name__ == "__main__":
    main()