[백준] 2805번 나무 자르기: Python

 

 

문제 해결 포인트

높이가 몇일 때 나무의 잘린 부분의 합이 M이 되는지 계산해야되는 문제입니다. 높이를 1씩 올리면서 언제쯤 최적화가 되는지 확인할 수도 있지만, 주어진 숫자가 너무 크기 때문에 시간초과가 나게 됩니다. 높이를 1씩 올린다는 아이디어는 탐색과 관련이 있습니다. 또한 나무들의 최소 높이와 최대 높이가 정해져 있기 때문에 높이를 무한정 높이는게 아니라 정해진 범위 내에서 탐색한다는 사실을 알 수 있습니다.

바로 여기에서 이분탐색의 아이디어를 떠올려야 합니다.

 

이분탐색

시간복잡도: O(logn)

범위를 절반씩 줄이면서 탐색합니다. 또한 리스트 내의 자료들이 정렬되어있어야 탐색이 가능합니다.

 

오름차순으로 자료가 정렬되어 있다고 가정할 때,

1. 찾아야되는 자료가 mid와 같은 지 확인합니다. mid는 low와 high의 중간에 있는 자료입니다.

2. 일치하면 탐색을 종료합니다. 일치하지 않으면

2-1) 찾아야되는 자료가 mid보다 클 때, low를 mid보다 한 칸 뒤에 있는 자료로 재설정합니다. high는 변하지 않습니다.

2-2) 찾아야되는 자료가 mid보다 작을 때, high를 mid보다 한 칸 앞에 있는 자료로 재설정합니다. low는 변하지 않습니다.

 

코드 작성

from sys import stdin

N, M = map(int, stdin.readline().rstrip().split())
heights = list(map(int, stdin.readline().rstrip().split()))

minH = 0
maxH = max(heights)
mid = 0

while minH <= maxH:
    mid = (minH + maxH) // 2
    heightSum = 0

    for i in heights:
        heightSum += (i-mid) if (i >= mid) else 0

    if heightSum >= M:
        minH = mid + 1
    elif heightSum < M:
        maxH = mid - 1

print(maxH)

heightSum이 M과 같아도 탐색을 더 진행해야 합니다. '적어도 M미터의 나무'를 집에 갖고가야 하기 때문입니다.

minH<=maxH를 만족한다면 더 큰 값의 mid를 탐색해도 좋으며 minH>maxH가 되어버리는 모순적인 상황이 될때 while문을 종료하면 됩니다.