문제 링크

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

개요

• 이분 탐색으로 해결할 수 있는 문제이다.
• Python3을 사용하면 시간초과가 발생하므로 PyPy3를 사용한다.

문제 조건

• 일정 높이에 대해 모든 나무를 잘랐을 때, 조건을 만족하는 절단기의 최대 높이(H)를 구하는 문제이다.
• 잘린 나무의 길이의 합은 상근이가 필요로 하는 나무의 길이(M)보다 크거나 같아야 한다.

문제 해설

• 나무의 수(N)의 최댓값이 1,000,000이므로 모든 범위에 대해 반복하는 순차 탐색을 이용할 경우 시간초과가 발생한다.
• 시간 복잡도가 O(log n)인 이분 탐색을 이용하면 시간 복잡도가 O(n)인 순차 탐색을 쓰는 것보다 훨씬 빠르다.
• 이분 탐색은 중간값(md)을 기준으로 시작하여 조건에 따라
  최대/최솟값의 포인터(mx/mn)를 조정하는 탐색 알고리즘이다.
• 잘린 나무의 길이의 합(total)을 구할 때 잘리지 않은 나무에 대한 음수값을 포함하지 않도록 주의한다.
• 조건을 만족할 경우 최솟값(mn)을 중간값(md)보다 크게 맞추며,
  반대의 경우 최댓값(mx)을 중간값(md)보다 작게 조정한다.
• 이분 탐색을 마치면 최댓값(mx)에 조건을 만족하는 최대 높이(H)의 값이 남게 된다.

시간 복잡도

• 시간 복잡도가 O(log N)인 이분 탐색의 매 반복마다 시간 복잡도가 O(n)인 for문을 실행하므로
  시간 복잡도는 O(N log N) 이상이 된다.
• N의 최댓값 1,000,000에 대해 20,000,000번이 넘는 연산이 실행되므로 Python3으로는 시간 제한 1초를 초과한다.
• PyPy3에 대한 이해가 깊은 편이 아니라 자세한 설명은 어렵지만,
  메모리를 더 사용하는 대신 코드를 캐싱하는 PyPy3를 사용하면 시간 제한 안에 해결할 수 있다.

해설 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

N, M = map(int, input().split())
trees = list(map(int, input().split()))
mn, md, mx = 0, 0, max(trees)

while mn <= mx:
    md = (mx + mn) // 2
    total = 0
    for tree in trees:
        total += tree - md if tree > md else 0

    if total >= M:
        mn = md + 1
    else:
        mx = md - 1
print(mx)