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

문제

이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

풀이(틀림/시간초과)

• 중간에 합을 구하다가 M을 넘은 것 같으면 어차피 더 계산해볼 필요가 없기 때문에 break 해줘야 하는데 무조건적으로 다 더해서 시간초과

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

start, end = barrel[0], barrel[-1]
mid = 15
while 1:
    mid = (start + end) // 2
    sumV = sum([bar - mid if bar - mid > 0 else 0 for bar in barrel])
    if sumV == M:
        res = mid
        break
    elif sumV > M:
        start = mid
    else:
        end = mid

print(res)

• 합이 M을 넘는 값을 가지는 값들 중에 최대값을 구하는 과정이기 때문에 현재 mid값을 기준으로 잘랐을 때 합이 M보다 크다면 이 mid값(=높이)도 M을 넘는 값을 가지는 값들에 포함이며 앞으로는 이 조건을 만족하면서 동시에 이보다 더 큰 값이 있는가를 찾아야 하기 때문에 start 값을 mid로 바꿔서 이 조건 내에서 재탐색을 한다.
• 만약 mid에서의 합이 M과 동일하다면 탐색의 끝에 결국 mid값이 출력되게 되어있음.
• start나 end값을 mid 값으로 초기화하게 되면 start end 값이 최종적으로 1 차이를 둔 두 개의 값 사이에서 무한대로 왔다갔다 하기 때문에 start+1 < end 상태가 되면 반복문 종료

풀이1

• 가장 기본적인 이분탐색 방식
• mid일때의 합이 M이어도 건너뛰고 다음 값부터 계산하게 되는데 최종적으로 end값이 mid-1을 가지기 때문에 end를 출력하면 제대로 된 mid값을 구할 수 있음

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
    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(end)

풀이2

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)