백준
백준 2805 나무 자르기 (파이썬)
chldkato
2020. 4. 27. 15:41
https://www.acmicpc.net/problem/2805
2805번: 나무 자르기
문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따
www.acmicpc.net
1. 최소값 0, 최대값은 가장 큰 나무 높이로 설정하여 이분탐색을 수행한다
2. 현재 중간값으로 모든 나무를 베었을 때 구할 수 있는 나무의 길이를 tree에 저장하여 m과 비교한다
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = list(map(int, input().split()))
left, right, ans = 0, max(a), 0
while left <= right:
mid = (left + right) // 2
tree = 0
for i in range(n):
if mid < a[i]:
tree += a[i] - mid
if tree >= m:
ans = mid
left = mid + 1
elif tree < m:
right = mid - 1
print(ans)