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

※ 문제

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

※ 문제 유형

이분 탐색, 매개 변수 탐색 (SILVER_2)

※ 나의 풀이

• 이분 탐색으로 문제 해결
• N, M의 입력 제한이 범위가 크므로, 시간 복잡도 고려 필수

import sys

N, M = map(int, sys.stdin.readline().split())

trees = list(map(int, sys.stdin.readline().split()))
trees.sort()
low, high = 1, trees[-1] #max(trees) - 시간 초과

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

    total = 0

    for tree in trees:
        if tree > mid:
            total += tree - mid

    if total >= M:
        ans = mid
        low = mid + 1
    else:
        high = mid - 1
print(ans)

 

※ 주의 사항

• low 는 최소한의 값인 1
• high 최대 값
  • max(trees)로 할 경우, 시간 복잡도 O(N)
  • trees.sort() 후 trees[-1]을 통하여 정렬된 값들 중 마지막 값(최대 값)을 가져오는 경우, 시간 복잡도 O(N log N) (정렬) + O(1) (리스트 값 호출) = O(N log N)

따라서 max(trees)를 사용하는 경우보다 trees.sort() 후 trees[-1]을 사용하는 경우가 이 문제에서 더 적합하며, 시간 복잡도 측면에서도 효율적입니다