하... 벨로그 오류 너무 심해서 짜증난다.

나무 자르기 - 2850번

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

풀이

기본적인 이분탐색(binary search)법을 통해 풀 수 있다.
처음 제출한 답안은 다음과 같다. 아래의 답안은 시간초과로 오답처리되었다.

import sys  
input = sys.stdin.readline
N, M = input().split()
N = int(N)
M = int(M)
heights = list(map(int, input().split()))
result = 0

def tree_binary_search(arr, start, end):
    global result
    while start<=end:
        mid = (start+end)//2
        sum = 0
        for i in arr:
            if i > mid:
                sum += i-mid
        if sum < M:
            end = mid
        else:
            result = mid
            start = mid
    return result

print(tree_binary_search(heights, 0, max(heights)))

0과 주어진 나무들의 키 중 최대를 각각 처음 탐색의 기준으로 삼는다. 고로 처음 탐색의 mid값은 0과 최대 나무의 키의 합의 반, 즉 최대 나무의 키의 반값이다. 수식화하면 mid = (start+end)//2 즉 탐색범위 시작과 끝 값을 이분한 "몫"이다.

-> 이제 인자 arr로 받는 각 나무들의 키를 밭복문으로 mid와 대조하여 만약 각 나무의 키가 mid보다 클 시 그 차이를 sum에 차곡차곡 도합한다.

1.->이때, 그 도합된 sum이 목표 재단값인 M보다 크거나 같으면 result에 그 sum을 임시저장한다. 이후 재탐색한다.
2.->이때, 그 도합된 sum이 목표 재단값인 M보다 작다면 그것은 우리가 원하는 값에 해당되지 않으므로 이후 재탐색한다.

방금 두 경우는 모두 while문의 처음으로 돌아가 다시 범위 안을 재탐색하는 수행을 할 예정이나, mid값으로 자른 재단의 합 sum이 목표 재단값 M보다 작을 시if sum < M:, 현재의 mid값이 이분하고 있는 탐색범위 둘 중 mid값보다 작은 범위 안에, 즉 그래프 상 왼쪽에 답이 있다는 뜻. 고로 탐색범위의 시작은 아까와 같이 0, 끝을 현재의 mid으로 재설정해준다.
반대로 mid값으로 자른 재단의 합 sum이 목표 재단값 M보다 크거나 같을 시 else:==if sum >= M:, 현재의 mid값 및 sum값에 대한 경우가 답일 확률이 있으므로 result에 현재 mid값을 기록, 탐색범위를 좀 더 좁혀 재탐색하는 것이다. 이 경우 현재의 mid값이 이분하고 있는 탐색범위 둘 중 mid값보다 큰 범위 안에, 즉 그래프 상 오른쪽에 답이 있을 확률이 있는 것이다. 그러므로 이번엔 탐색의 start값을 현재의 mid값으로 재설정하여 탐색범위를 이분하는 것이다.

그런데 이 풀이는 시간초과로 탈락하였다. 원인은 거듭되는 탐색 범위의 이분할로 탐색 범위의 시작인 start값과 범위의 끝인 end값이 어느 순간 교차해야지, 즉 end가 start의 이하가 되는 순간이 와야지 while문이 끝나며 탐색이 종료되는데, 위의 식으로 풀다보면 end와 start의 값이 점점 mid에 수렴하다가 더이상 변동되지 않고 고정되어 while문 안을 영원히 돌게 된다....

그래서 아래와 같이 코드를 수정하여 통과할 수 있었다.

import sys  
input = sys.stdin.readline
N, M = input().split()
N = int(N)
M = int(M)
heights = list(map(int, input().split()))
result = 0

def tree_binary_search(arr, start, end):
    global result
    while start<=end:
        mid = (start+end)//2
        sum = 0
        for i in arr:
            if i > mid:
                sum += i-mid
        if sum < M:
            end = mid-1
        else:
            result = mid
            start = mid+1
    return result

print(tree_binary_search(heights, 0, max(heights)))

이렇게 되면 재탐색 범위 설정 시 언젠가 start값과 end값이 교차할 수 있게 된다.