[백준 알고리즘: python 3] #2805 - 나무자르기(이분 탐색 스터디)

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

 

2805번 문제는 백준 알고리즘의 이분 탐색 단계에 속하는 비교적 낮은 성공률의 문제입니다. 문제의 성공률이 낮아 어려울까 생각을 했었는데, 이분 탐색의 개념을 그대로 적용할 수만 있다면 난이도가 높은 문제는 아니었습니다.

 

이분 탐색은 매 스텝마다 탐색의 범위를 절반씩 줄여나가며 정답으로 가까워지는 탐색 방법으로 탐색 방법 중 매우 빠른 속도를 자랑하는 알고리즘입니다. 흔히, 오름차순으로 이루어진 배열에서 원하고자 하는 값을 찾을 때 이분 탐색을 사용해 빠르게 찾아내는 것을 예시로 들어 설명하는 것 같았습니다. 저는 이분 탐색의 개념을 이 블로그에서 쉽게 알 수 있었는데요, 그림으로 차근차근 설명이 되어 있으니 공부하실 때 참고하시면 좋을 것 같아요.

 

요약하자면 이렇습니다.

 

1. 이분 탐색의 시작은 탐색 범위의 가장 작은 값(low_value)과 가장 큰 값(high_value)을 설정합니다. 찾고자 하는 값을 answer라고 부릅니다.
2. low_value와 high_value의 평균의 내림값을 pivot이라고 하고 이 값과 answer를 비교합니다. 예를 들어, low_value가 10, high_value가 21이라면 pivot은 15가 됩니다.
   1. 만약 anwer가 pivot보다 크다면 low_value를 pivot+1로 바꿉니다. 왜냐하면, 찾고자 하는 값이 low_value와 high_value 의 평균값보다 크기 때문에 평균 값, 즉 pivot 보다 작거나 같은 값은 정답의 후보가 될 수 없기 때문입니다.
   2. 만약 answer가 pivot보다 작다면 high_value를 pivot-1로 바꿉니다. 이유는 위의 경우와 반대이기 때문이겠죠.
   3. high_value가 low_value보다 크거나 같아지는 상황이 올 때까지 위 1, 2번을 반복합니다.

이런 식이 됩니다. 위의 2번에서 탐색의 범위가 매 순회마다 절반씩 줄어드는 것을 확인할 수 있습니다. 이렇기 때문에, 탐색의 범위가 아무리 넓다고 해도 절반씩 줄여나갈 수 있어서 빠른 탐색이 가능한 것입니다.

 

Hint!

이 알고리즘을 나무 자르기 문제에 잘 적용을 하려면, 위의 설명에서 low_value와 high_value를 와 정답과 비교할 pivot을 어떻게 설정할 지가 가장 중요합니다. 이 문제에서 찾아야 하는 것은 최대로 높게 설정할 수 있는 절단기의 높이기 때문에 초기에 값을 설정 할 때는 low_value가 0, high_value는 주어진 나무 높이 중 최댓값으로 설정하면 됩니다.

 

당연히 answer는 문제에서 주어지는 M 값이 되고, 가장 중요한 pivot값은 절단기의 low_value와 high_value의 평균값이 되겠네요. 하지만 비교를 할 때는, 위의 설명과는 달리 M값과 pivot 값 자체가 아니고 이 pivot값의 절단기 높이로 나무를 잘랐을 때 상근이가 얻을 수 있는 나무의 총 길이가 되겠습니다. 이 둘을 계속 비교해 가며 low_value, high_value를 업데이트 하면 쉽게 문제를 풀이할 수 있습니다.

어떻게 업데이트 해야할까요? 절단기의 높이가 낮아지면 질수록 나무의 길이는 늘어날 수밖에 없고, 높아지면 나무의 길이는 작아질 수 밖에 없는 규칙이 있기 때문에 low_value와 high_value 의 pivot으로 나무를 잘라서 얻은 길이가 M(필요한 나무의 길이)보다 크면 high_value를 pivot-1로줄이고 반대의 경우에는 low_value를 pivot+1로 늘리는 방식이 됩니다. 이런 식으로 탐색의 범위를 좁혀서 얻은 pivot값이 정답이 되는 것이죠.

 

한가지 주의할 점은, 이 문제가 정확히 값을 찾아내는 탐색 문제가 아닌 자른 나무의 총 길이가 M보다 큰 상황에서의 최대 절단기 높이 이기 때문에, 반복문이 돌아가면서 pivot값이 M보다 크게 될 때마다 정답을 업데이트 해야 한다는 것입니다. 쉽게 말하면, 현재 절단기 높이로 M 이상의 나무를 벨 수 있다면 정답의 후보가 될 수 있다는 것입니다. 이 절단기 높이를 계속해서 줄여나가다가 반복문이 끝날 때 저장되어 있는 정답이 이 문제의 정답이 되겠죠?

 

사실 코드는 그렇게 길지 않습니다. 위에서 설명한 부분들이 코드에 잘 녹아져 있고 말했듯이 길지 않으니 금방 이해하실 수 있을거에요! (설명보다 코드보는게 이해가 더 빠를지도...) 그림으로 자세히 설명해보려고 했지만... 오늘은 귀찮아서....ㅎㅎ 어렵지 않으니 요정도로 해놓겠습니다!

 

아래의 코드로 성공하였습니다.

import sys

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

cut_low = 0
cut_high = max(trees)
result = 0
while cut_high >= cut_low:
    pivot = int((cut_low + cut_high) / 2)
    # pivot의 길이로 자를 수 있는 나무의 총 길이
    cut_tree = sum([x - pivot if x >= pivot else 0 for x in trees])
    # 비교
    if cut_tree >= M:
        cut_low = pivot + 1
        # 이 높이로 M이상의 나무를 자를 수 있고, 저장된 정답보다 크다면 이 높이로 정답을 업데이트
        if result < pivot: result = pivot
    elif cut_tree < M: cut_high = pivot - 1

print(result)