2805 나무 자르기

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

2805번: 나무 자르기

 

내 풀이(맞음)

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

start = 0
end = max(ary)
answer = 0

while (start <= end):
    mid = (start+end) // 2
    
    total = 0
    for i in range(n):
        if ary[i] > mid:
            total += ary[i] - mid
    
    if m > total:
        end = mid - 1
    else:
        start = mid + 1
        answer = mid
print(answer)

어제 "이것이 취업을 위한 코딩 테스다"에서 푼 문제와 굉장히 유사한 문제라서 쉽게 풀 수 있었다. 절단기의 범위는 0부터 가장 큰 나무의 길이이다. 따라서 start가 0, end는 가장 큰 나무의 길이로 두고 반복적인 이진 탐색을 해주면 된다. 그리고 일단 절단한 길이가 m보다 크면 그 절단기의 길이를 answer에 계속 기록하는 형태로 문제를 풀면된다.

 

-어제 풀었던 유사한 문제

https://shortcoding.tistory.com/220

떡볶이 떡 만들기