[PY] 2805 : 나무 자르기

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

뭘 해달란거야 하고 쭉 보니, 일단은 나무 자를 정도를 특정 할 수 있어야 할 것 같았다.
특정하는 방법 중 가장 빠른 방법은 이분 탐색이다는걸 알고 있다면 뭘 해야할지 조금씩 감이 잡힌다.

간단하게 풀이하면 이렇다.

1. 입력받은 나무 길이 중 최대 수치를 따로 갖고 있기로 한다. 이것을 maxTree라고 하자.
2. 0부터 maxTree는 자를 수 있는 절단기의 선택 범위가 된다. 이중에서 어떻게 자르겠다라고 가정했을 때, 자른 후의 나타난 내용을 확인한다.
   • 이 때 생각 해야 할 것은, 절단기의 높이를 정해두었는데 그보다 낮은 나무에 대해선 잘리지 않을 것이다. 그래서 나무의 높이와 절단기의 높이를 계산 했을 때, 음수로 넘어가는건 무효 숫자로 판단하고 빼야 한다는 생각을 했다.
3. 핀트는 M보다 같거나 많은 나무를 얻을 수 있는 선택지를 생각해야 한다. 그래서 일반적인 이분 탐색에서 다소 달라진 형태를 취한다.

허용 범위나 검색 범위를 새롭게 지정하던 중에 석연찮았던게 많아서 조금 다난 했다.

import sys
sys.setrecursionlimit(10**8)
treeListCnt, requireTree = list(map(int, sys.stdin.readline().strip().split()))
treeList = list(map(int, sys.stdin.readline().strip().split()))[:treeListCnt]
result = []

treeList.sort()
maxTree = treeList[len(treeList) - 1]

def BinarySearch(strt, end):
    global result
    mid = (strt + end) // 2
    if(strt > end):
        return


    total = 0
    # mid에 대한 값을 treeList 전체에 대조하여 그 결과가 requireTree 와의 차이를 찾아야한다.
    for i in range(len(treeList)):
        addVal = treeList[i] - mid
        if(addVal < 0):
            continue

        total += addVal
        # 15 10 17 20인데 18이 들어오면
        # if(treeList[i]가 mid보다 작으면 패스)
    if total >= requireTree:
        result.append(mid)
        return BinarySearch(mid + 1, end)
    elif total < requireTree:
        # 잘린 값이 너무 적으면 자르는 양을 늘려야지 않나?
        return BinarySearch(strt, mid - 1)


BinarySearch(0, maxTree)
print(max(result))