[이분탐색 / python] 백준 2805. 나무 자르기

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

2805번: 나무 자르기

 

문제 해석

해당 문제는 "넓은 탐색 범위에서 특정 숫자를 찾는 것"이므로 시간복잡도를 고려했을 때 이분탐색으로 풀어야 한다.

 

 

문제 풀이

첫 번째 시도

import sys
input = sys.stdin.readline

"""real input"""
n, m = map(int, input().split())
li = list(map(int, input().split()))

""".text"""
high = max(li)
low = 0
while low <= high:

    res = 0
    mid = int((high + low)/2)
    for i in li:
        if (i - mid) >= 0:
            res += (i - mid)
        else:
            res += 0
    if res == m:
        break
    if res > m:
        low = mid + 1
    elif res < m:
        high = mid - 1
print(mid)

이분탐색 로직을 이용하여 가장 높은 토막을 찾아내면 되겠다고 생각했고, 한 지점으로 수렴하면 그 mid 값을 뽑아내면 되겠다고 판단했다. 하지만 출력을 해보니 위 로직으로는 적절한 높이가 구해지지 않았다.

 

그리고 무엇보다 조건을 만족할 때 최대한 나무를 덜 베어내야 한다는 점을 간과했다.

 

두 번째 시도

import sys
input = sys.stdin.readline
from random import *

""".input"""
n, m = map(int, input().split())
li = list(map(int, input().split()))

""".text"""

high = max(li)
low = 0
while low <= high:
    res = 0
    mid = int((high + low)//2)
    for i in li:
        if (i - mid) >= 0:
            res += (i - mid)
        else:
            res += 0
    # if res == m:
    #     break
    if res >= m:
        low = mid + 1
    else:
        high = mid - 1
print(high)

최대한 높은 값을 뽑아내야 하므로,

res == m일 때 바로 멈추는 것이 아니라 while 문의 조건에 따라 탈출하게 설계하고 최대한 잘라내는 높이를 높여야 하므로 하한을 올리는 로직에 등호를 추가한다. 이를 통해 가장 높은 지점에 high와 low가 수렴하게 되고, 마침내 한 지점으로 수렴했을 때 마지막으로 low지점이 high를 넘어서면서 while이 탈출하게 된다. 이 때의 high를 출력하면 정확한 값을 뽑아낼 수 있다.

 

마지막 지점에서도 답이 맞으면 low는 수렴한 지점에서 +1 된 값이므로 정확하지 않고, 답이 아니면 직전 값이 정답이니 high가 다시 수렴 지점으로 내려가므로 high를 뽑아야 한다. mid의 경우에도 절반으로 나눈 값이므로 마지막 지점에서는 올바른 값을 나타내고 있지 않다.

5 20
4 42 40 26 46

# print("b", high, low, mid, res, m)
# if res >= m:
#     low = mid + 1
# else:
#     high = mid - 1
# print("a", high, low, mid, res, m)
    
b 46 0 23 62 20
a 46 24 23 62 20
b 46 24 35 23 20
a 46 36 35 23 20
b 46 36 41 6 20
a 40 36 41 6 20
b 40 36 38 14 20
a 37 36 38 14 20
b 37 36 36 20 20
a 37 37 36 20 20
b 37 37 37 17 20
a 36 37 37 17 20

# print(high)
36