[백준] 2805 : 나무 자르기

문제

계속 문제났던 부분

더이상 검색할 게 없는 경우(정확하게 잘리진 않는 경우)에 상근이는 항상 나무를 가져갈 수는 있고 절단할 수 있는 높이의 최댓값을 구해야 하므로 end를 리턴해줘야 한다.
리턴값이 None이 될 수는 없기 때문이다!!!!

풀이

import sys
n, m = map(int, sys.stdin.readline().split())
tlist = list(map(int, sys.stdin.readline().split()))


def bsearch(start, end, target): # mid는 절단기의 길이
    if start > end :
        return end
    
    mid = (start + end) // 2
    
    a = 0 # 절단기에 자르고 남은 나무 길이
    for i in tlist:
        if i >= mid:
            a += i - mid
    
    if a == target: # 절단기에 자르고 남은 나무 길이와 원하는 나무 길이가 같을 때
        return mid
    if a > target: # 절단기에 자르고 남은 나무 길이가 원하는 나무 길이보다 길 때는 덜 잘라야 하므로 절단기 길이 길게
        start = mid + 1
    if a < target:
        end = mid - 1
    
    return bsearch(start, end, target)
    
print(bsearch(0, max(tlist), m))

22.04.12 다시 풀어보기

딱 맞게 잘라지지 않을 경우도 있음!
이때 answer 변수를 따로 두고 mid값을 넣어두면 어차피 최댓값으로 수렴하면서
answer에 sum >= target에 부합하는 최대 mid값이 적용됨!

import sys

N, M = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))

def bsearch(target):
    start = 0
    end = max(tree)

    while start <= end:
        mid = (start + end) // 2 # 절단기 높이
        
        sum = 0
        for i in tree:
            if i >= mid:
                sum += i - mid
        
        if sum < target: # 더 많이 잘라줘야 -> 절단기 길이 작아져야
            end = mid - 1
        elif sum >= target: # 더 적게 잘라줘야 -> 절단기 길이 길어져야
            start = mid + 1
            answer = mid 
            # 딱 맞게 잘라지지 않을 경우도 있음! 
            # 이때 answer 변수를 따로 두고 mid값을 넣어두면 어차피 최댓값으로 수렴하면서
            # answer에 sum >= target에 부합하는 최대 mid값이 적용됨!
            
    return answer

print(bsearch(M))