[Python | 백준] 2805번: 나무 자르기

 

 

문제 요약

높이 H 지정 (0~양의 정수)

H보다 큰 나무는 H 위의 부분이 잘리고, 낮은 나무는 잘리지 않는다.

적어도 M미터의 나무를 집에 가져가기 위한 절단기 높이의 최댓값

나무의 수 N (1 ≤ N ≤ 1,000,000)
가져가야 하는 길이 M (1 ≤ M ≤ 2,000,000,000)

-> input값이 매우 크다. 시간 복잡도를 신경 써야 한다는 힌트이다.

 

첫번째 시도: 브루트 포스(완전탐색) - 시간 초과

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
trees = list(map(int, input().split()))
trees.sort(reverse=True)
h = trees[0]-1
for i in range(h, 0, -1):
    tmp_trees = [tree - i for tree in trees if tree - i > 0]
    total = sum(tmp_trees)
    if total >= M:
        print(i)
        break

첫번째로는, 시간복잡도를 신경쓰지 않고 완전탐색으로 시도해보았다.

모든 가능한 절단 높이에 대해 하나하나 확인하면서 적합한 조건을 만족하는지 검사한다.

 

이 코드의 시간 복잡도를 분석해보면 다음과 같다:

1. 가장 높은 나무의 높이를 h로 정의한다. (h = trees[0] - 1).
2. 코드는 h부터 1까지 각 높이 i에 대해 나무들을 순회하면서 tree - i가 양수인 경우에만 나무 길이를 계산한다.
   -> 즉, 모든 가능한 높이에 대해 모든 나무를 검사하게 된다.
3. 최악의 경우, 모든 높이 i에 대해 전체 나무 리스트를 검사해야 하므로, N이 나무의 수이고 H가 최대 나무 높이라 할 때,
   시간 복잡도는 대략 O(N * H)이다.

이러한 접근 방식은 나무의 높이가 높거나 나무의 수가 많은 경우 매우 비효율적일 수 있다.

 

 

이진 탐색 풀이

따라서 실제 적용 시나리오에서는 이진 탐색을 활용하는 것이 더 적합하다.

이진 탐색을 사용하면 O(N log H)의 시간 복잡도로 문제를 해결할 수 있다.

높이의 범위를 절반씩 줄여 나가면서 필요한 길이 이상의 나무를 얻을 수 있는 최소 높이를 찾는 방식이다!

 

import sys
input = sys.stdin.readline

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

low, high = 0, max(trees)

while low <= high:
    mid = (low + high) // 2
    total = sum((tree - mid) for tree in trees if tree > mid)

    if total >= M:
        low = mid + 1
    else:
        high = mid - 1

print(high)