[백준/Python] 2805 나무 자르기

 

📌 문제 탐색하기

• 상근이가 필요로 하는 나무 길이는 M미터 (1 ≤ M ≤ 2,000,000,000)
• 나무 한 줄에 N개의 나무(1 ≤ N ≤ 1,000,000) 존재
• 나무 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0
• 목재절단기에 높이 H 지정 -> 톱날이 땅으로부터 H미터 위로 올라가서 한 줄에 연속해있는 나무 모두 절단
  
  • 높이가 H보다 큰 나무는 H 위의 부분이 잘리고, 낮은 나무는 잘리지 않음
• 상근이는 높이 H보다 큰 나무의 잘린 부분의 나무를 들고 감
• 적어도 M미터의 나무를 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값 구하기 

나무의 최대 높이가 1,000,000,000이므로, 높이를 한칸씩 줄여가면서 상근이가 M미터의 나무를 가져갈 수 있는지 확인한다면 높은 확률로 시간 초과가 날것이다. 따라서, 목제 절단기 높이 범위를 [0 ~ 나무들 중 최대 높이]로 설정하고, 이분탐색을 수행해서 조건을 만족하는 높이의 최댓값을 찾는 것이 옳은 판단일 것이다.

이분 탐색을 수행하는데 O(log(나무 높이의 범위))의 시간복잡도가 소요되고, 각 높이에 대해 나무가 얼마나 절단되는지 확인해야하므로 N개의 나무를 순회해야해서 O(N)의 시간이 소요된다. 즉, 최종 시간복잡도는 O(Nlog(나무 높이의 범위))가 되므로 시간 내에 충분히 문제를 해결할 수 있다.

---

📌 코드 설계하기

1. 나무의 수 N, 나무의 길이 M 입력받기
2. 나무들의 높이 trees 리스트로 입력받기
3. low를 0, high를 입력받은 나무 높이 중 가장 큰 값으로 설정하고 이분탐색 수행
4. 각 탐색 과정에서 mid=(low+high)//2가 해당 과정의 절단기 높이가 되고, trees를 순회하며 총 가져갈 수 있는 나무 길이 tree_length 구하기
5. tree_length가 M보다 크거나 같다면, 정답 후보이므로 result에 mid값을 저장 후 더 큰 값이 가능한지 확인하기 위해 low를 mid+1로 변경하고, 아니라면 high를 mid-1로 변경한다.
6. low가 high를 넘을 때까지 반복하고 그때의 result 값을 출력한다.

---

📌 정답 코드

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

low = 0
high = max(trees)
result = 0

while low <= high:
  mid = (low + high) // 2

  tree_length = 0
  for tree in trees:
    if tree > mid:
      tree_length += tree - mid
  
  if tree_length >= M:
    result = mid
    low = mid+1
  else:
    high = mid-1
  
print(result)