[알고리즘] 백준 2805 : 나무 자르기 - S2

2023.05.10 풀이

import sys
input=sys.stdin.readline

n,m=map(int, input().split())
arr=list(map(int, input().split()))
arr.sort()

def bs(start, end, m):
    mid=(start+end)//2
    if start>end:
        return mid
    sum=0
    for i in arr:
        if i>mid:
            sum+=(i-mid)
    if sum==m:
        return mid
    elif sum>m:
        return bs(mid+1, end, m)
    else:
        return bs(start, mid-1, m)

print(bs(0, max(arr), m))

• sum 부분을 반복문으로 구현하는게 맞을지 고민함
  + 기준치보다 큰 부분만 자르기 때문에 if문이 필요한데 이 부분 구현에서 오래걸림

---

다른 풀이

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

start=0
end=max(arr)

res=0
while (start<=end):
    total=0
    mid=(start+end)//2
    for i in arr:
        if i>mid:
            total+=i-mid
    if total<m:
        end=mid-1
    else:
        res=mid
        start=mid+1

print(res)

N, M = map(int, input().split())
tree = list(map(int, input().split()))
start, end = 1, max(tree) #이분탐색 검색 범위 설정

while start <= end: #적절한 벌목 높이를 찾는 알고리즘
    mid = (start+end) // 2
    
    log = 0 #벌목된 나무 총합
    for i in tree:
        if i >= mid:
            log += i - mid
    
    #벌목 높이를 이분탐색
    if log >= M:
        start = mid + 1
    else:
        end = mid - 1
print(end)

---

check point

• 전형적인 이진탐색 문제이자 파라메트릭서치 유형의 문제.
  파라메트릭 서치 : 최적화 문제를 결정 문제로 바꾸어 해결하는 기법
  원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제 : 이진탐색으로 해결
  , 반복문으로 구현이 더 간단함