링크텍스트
목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다.
예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
이 문제도 이진탐색으로 푸는 문제이다.
start 값을 0으로 놓고(모든 나무를 합한 길이만큼 절단해야 할 수도 있음)
end 값은 나무 길이들 중 최대로 긴 나무의 길이를 넣는다.(그 이상은 의미가 없으므로)
이렇게 start와 end를 설정해 놓은 뒤, 중간값인 mid를 구해서 이와 비교해가면서 영역을 좁혀간다.
최종적으로 end 값을 출력하면 된다.
n, m = map(int, input().split()) # 나무의 수, 잘라야 하는 나무의 총 길이
height = list(map(int, input().split())) # 나무의 높이
start = 0
end = max(height)
while start <= end:
mid = (start + end) // 2 # 절단기에 설정할 높이
total = 0 # 자른 나무의 길이를 더할 변수
for i in height:
if i > mid: # 나무가 절단기에 설정한 높이보다 클 때
total += (i - mid) # 그 나무를 자른 길이를 더한다.
if total >= m: # 자른 나무의 길이의 총합(total)이 잘라야 하는 나무의 길이보다 클 때
start = mid + 1 # start값을 지금 설정한 절단기 설정값보다 크게 한다.
else: # 작을 때
end = mid - 1 # end값을 절단기 설정값보다 작게 한다.
print(end)