[BOJ] 2805. 나무 자르기 (🥈, 이분탐색)

이분 탐색

• 정렬되어 있는 리스트에서 찾고자 하는 값을 탐색할 때 범위를 절반씩 좁혀가며 찾는 방식
• 일반 탐색(Brute-Force)은 O(N)인 반면에 이분 탐색은 O(logN) (단, 리스트의 길이가 짧은 경우는 일반 탐색이 더 빠를 수 있음)
• start, end 의 값을 정해놓고 mid = (start + end) // 2로 하는 것이 일반적
• 찾는 값이 mid 보다 크다면 mid~end (오른쪽) 사이에서 탐색을 해나가야 하므로 start=mid+1, 반대로 찾는 값이 mid보다 작다면 start~end (왼쪽) 사이에서 탐색을 해나가야 하므로 end=mid-1로 값을 변경해줌

문제

이 문제 역시 이분 탐색으로 푸는 것은 맞지만 최대값을 찾아야 한다는 조건이 있음

• 즉 mid가 조건에 만족하는 값이라고 해도 조건을 만족하면서 mid보다 큰 값 = mid의 오른쪽에 위치한 값을 찾아야 한다. 즉 결국은 한 번 이상은 반드시 오른쪽을 탐색해야만 한다는 것
• 이 경우는 최대값이기 때문이고 최소값인 경우는 왼쪽이 된다.

풀이1

• 마지막에 찾은 값을 mid가 아닌 start로 한 이유는 어차피 start라는 값이 mid로 한 번 옮겨진 값이며 이 start는 곧 조건을 만족하는 우리가 찾는 마지막 값이 될 수 있다. 우리는 이 사실을 모르는 상태로 오른쪽에서 계속해서 더 최대값이 될 수 있는 값이 있나를 탐색해나가게 되는데 만약 탐색해서 값이 없게 된다면 범위는 점점 이 start쪽으로 좁혀오게 되고 조건(start+1<end)을 만족하지 못하게 되면 반복문을 탈출하게 된다.
• 이 조건에서는 start와 end의 위치가 변하지 않은 상태에서 끝나게 되는데 이 때문에 우리는 start의 위치를 우리가 찾는 최대값이라 결정지어도 되는 것이다(end 일 수는 없는게 end는 end가 되기 직전에 mid 값이였는데 그 값이 조건을 만족못해서 end값으로 덮어씌워진 것이기 때문에)

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
tree = list(map(int, input().split()))

start, end = 0, max(tree)
while start + 1 < end:
    mid = (start + end) // 2
    s = 0
    for t in tree:
        if t > mid:
            s += (t - mid)
        if s > M:
            break
    if s >= M:
        start = mid
    else:
        end = mid

print(start)

• 일반 이분탐색이 아닌 방식으로 답 도출

lst = [1, 3, 5, 7, 9]
lo = 0
hi = 4

while lo + 1 < hi:
    mid = (lo + hi) // 2
    print(lo, hi, mid)
    if lst[mid] == 7:
        print('찾음!')
        break
    elif lst[mid] > 7:
        hi = mid 
    else:
        lo = mid

• 오른쪽에 답이 있는 경우만 찾을 수 있는 이분 탐색

풀이2

• 이 경우는 end로 반환값을 줘야 하는데 그 이유는 간단하다. 위와 다르게 start와 end의 위치가 뒤바뀌어야만 반복문이 종료되고, 계속해서 start의 위치가 mid 이상으로 옮겨지기 때문에 만약 우리가 찾는 최대값이 mid가 마지막이였다고 해도 우리는 그 사실을 모른채로 start를 mid+1로 옮기게 되는데 결국에는 탐색 끝에 값을 찾을 수 없어서 범위가 다시 좁혀져 오게 되고 (우리가 찾는 값) < start <end 이 순서대로 놓여지게 된다
• 반복문은 start와 end 순서가 바뀌는 순간 끝나게 되는데 end가 start보다 -1인 값을 가지게 되면 그게 바로 우리가 찾는 mid 값이 된다(start=mid+1 이였으니까)

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
tree = list(map(int, input().split()))

start, end = 0, max(tree)
while start <= end:
    mid = (start + end) // 2
    s = 0
    print(start, mid, end)
    for t in tree:
        if t > mid:
            s += (t - mid)
        if s > M:
            break
    if s >= M:
        start = mid + 1
    else:
        end = mid - 1

print(start, mid, end)