[python] 백준 2805: 나무 자르기

 

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

 

 

이분탐색 문제이다. 

" 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다. " 라는 부분에서  << m을 조절해야 한다 . 즉 이분탐색으로 탐색해야 높이 값에서 시간 초과가 나지 않도록 설정할 수 있을 것이라는 힌트를 얻었다. 이분탐색 문제임을 파악하였다면, 기본 메커니즘대로 코드를 작성하면 된다.

 

#백준 2805: 나무 자르기

#import dictionary

import sys

#binary search

def binary_search(start, end, target):

while start <= end:

mid = (start + end) // 2

sum = 0

for i in range(n):

if tree[i] > mid: #if height of tree is bigger than mid

sum += tree[i] - mid #add the difference to sum

if sum >= target: #if sum is bigger than target

start = mid + 1 #move start to mid + 1

else: #if sum is smaller than target

end = mid - 1 #move end to mid - 1

return end

#input/output

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

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

start = 0

end = max(tree)

print(binary_search(start, end, m))