💻 백준 2805: 나무 자르기

문제 소개 🧐

N개의 나무가 일렬로 있을 때, 상근이가 M미터의 나무를 가져가기 위해 절단기에 설정할 수 있는 높이(H)의 최댓값을 구하는 문제. 절단기 높이 H보다 높은 나무는 H 위 부분이 잘리고, 낮은 나무는 잘리지 않는다.

입력 📝

  • 첫째 줄에 나무의 수 N과 필요한 나무의 길이 M이 주어집니다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
  • 둘째 줄에는 N개의 나무 높이가 주어집니다. (0 ≤ 높이 ≤ 1,000,000,000)

출력 📤

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

제한 ❌

  • 1초, 256MB

첫 번째 시도: 선형 탐색 (시간 초과) 👊

Idea

절단기 높이 H를 0부터 1씩 증가시키면서, 각 H에 대해 잘린 나무의 총 길이를 계산하고 M과 비교했다. M보다 크거나 같아지는 순간의 H를 찾아 출력하는 방식이다.

Code

import sys

n, m = map(int, sys.stdin.readline().split())
tree_heights = list(map(int, (sys.stdin.readline().split())))

take_val = 1e11
h = 0
while take_val >= m:
    h += 1
    go_home_list = list(map(lambda x: x-h if x-h >= 0 else 0, tree_heights))
    take_val = sum(go_home_list)

print(h-1)

Result

  • 시간 초과 ⏰
  • H를 1씩 증가시키는 while 루프가 최악의 경우 M번 반복될 수 있고, 각 반복마다 map과 sum 연산으로 인해 O(N)의 시간이 소요된다. 따라서 전체 시간 복잡도가 O(M*N)이 되어 시간 제한을 초과했다.

두 번째 시도: 이분 탐색 (매개 변수 탐색) ✨

Idea

절단기 높이 H는 0부터 나무의 최대 높이까지의 범위에 존재한다. 이 범위 내에서 이분 탐색을 사용하여 최적의 H를 찾는다.
특정 H에 대해 잘린 나무의 총 길이가 M보다 크거나 같으면 H를 더 높일 수 있고,
M보다 작으면 H를 낮춰야 한다. 이분 탐색을 통해 total_wood >= m을 만족하는 H의 최댓값을 찾는다.

Code

import sys

n, m = map(int, sys.stdin.readline().split())
tree_heights = list(map(int, sys.stdin.readline().split()))

start, end = 0, max(tree_heights)
result = 0

while start <= end:
    mid = (start + end) // 2
    total_wood = sum(map(lambda x:x-mid if x>mid else 0, tree_heights))
    
    if total_wood >= m:
        result = mid
        start = mid + 1
    else:
        end = mid - 1

print(result)

Result

  • 성공! ✅
  • 이분 탐색을 통해 시간 복잡도를 O(N log H_max)로 줄여 효율적으로 문제를 해결했다. 특정 조건을 만족하는 최댓값/최솟값을 찾는 문제에 이분 탐색을 적용하는 것을 ‘매개 변수 탐색’ 이라고 한다.

개선할 부분 🤔

  • sum(map(...)) 부분은 파이썬 내장 함수로 효율적이지만, 경우에 따라서는 직접 for 루프를 돌며 합을 계산하는 것이 미세하게 더 빠를 수도 있다.
    하지만 가독성과 편의성을 고려하면 현재 코드를 작성했다.