[TIL] 백준 2805 - 나무 자르기 ( python )

📌 문제 탐색하기

 

N : 나무 개수, )

M : 가져가야 할 나무 길이

trees : N개의 나무 높이 리스트

 

 

상근이는 최소 M미터의 나무를 가져가기 위해 나무를 일정 높이에서 잘라야 합니다.

필요한 나무를 가져갈 수 있는 절단기 높이의 최댓값을 구하는 것이 핵심입니다.

잘린 나무의 길이의 합이 M 이상이어야 하며, 절단기의 높이를 조정하면서 가장 높은 값을 찾아야 합니다.

 

 

1 ≤ N ≤ 1,000,000

1 ≤ M ≤ 2,000,000,000

1 ≤ 나무 높이 ≤ 1,000,000,000

가능한 시간복잡도

1. 완전탐색
   
   • 0부터 제일 길이가 긴 나무(max(trees)까지 모든 절단기가 자를 나무의 높이를 순회하면서 자른 나무의 길이를 계산합니다.
   • 최악의 경우
     
     • max(trees) = 1,000,000,000
     • N = 1,000,000
     • 총 연산 횟수 = 1,000,000 * 1,000,000,000 = 10^15
   • 완전 탐색으로 코드를 설계할 경우 시간 초과가 납니다.
2. 이진 탐색 적용
   
   • 절단기로 자를 나무의 높이의 탐색하기 위해 0부터 제일 길이가 긴 나무(max(trees)로 설정하고 이진 탐색을 수행합니다.
   • 매 탐색마다 절단기로 자른 나무를 더해줍니다(최대 N번 연산)
     • length += tree - mid
   • 최악의 경우
     
     • log max(trees) = log(1,000,000,000) = 30
     • N = 1,000,000
     • 1,000,000 * 30 = 30,000,000
   • 3천만번으로 시간 내에 충분히 연산 가능합니다.

알고리즘 선택

이진 탐색을 사용하여 잘린 나무의 길이 합이 M 이상이 되는 최대 높이를 찾겠습니다.

---

📌 코드 설계하기

1. 문제의 Input을 받습니다.
2. start = 0, end = max(trees)로 설정합니다.
3. mid = (start + end) // 2에서 자른 나무의 길이를 계산합니다.
4. 잘린 나무 길이 합이 M 이상이면 더 높은 높이의 가능성 확인합니다.
   1. start = mid + 1 
5. 잘린 나무 길이 합이 M 미만이면 더 낮은 H 필요합니다.
   1. end = mid - 1 
6. 최종적으로 end가 자를 나무의 높이 최댓값이 됩니다.
7. end를 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

• 시간 초과 발생
  • tree 리스트를 인덱스로 접근
    
    • trees[i] 조회 시 인덱스 접근 비용이 추가로 발생합니다.
    • 리스트 크기가 1,000,000일 경우 성능 저하 발생합니다.
  • 설계를 수정합니다.
    • trees 요소를 직접 접근
      • 불필요한 인덱스 연산이 제거되어 전체적인 속도가 빨라집니다.

---

📌 정답 코드

import sys
input = sys.stdin.readline

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

start = 0
end = max(trees)

while start <= end:
    mid = ( start + end ) // 2
    length = 0

    for tree in trees:
        if mid < tree:
            length += tree - mid

    if length >= M:
        start = mid + 1
    else:
        end = mid - 1

print(end)