백준 2805번 나무 자르기

Intro

기본적인 이분 탐색 문제. 목재절단기의 적합한 높이를 이분 탐색으로 범위를 좁혀가며 찾아야 한다.

Solution

1. 찾고자 하는 높이가 될 숫자를 임의로 정한다. 반복할 때마다 범위를 줄여가며 숫자를 다시 정한다. (mid)
2. 해당 높이로 나무를 모두 자른다. 땅 밑으로 나무를 자를 수는 없다. (h)
3. 뺄셈 연산 후 나무의 길이의 합을 구한다. (add)
4. 합을 찾고자 하는 나무의 길이와 비교한다.
   4-1. 합이 m과 동일하면 현재의 mid 값이 정답이다.
   4-2. 합이 m보다 크면 정답이 될 수 있다. 개선의 여지가 있으므로 범위의 최솟값을 현재의 mid 값으로 재설정한다.
   4-3 합이 m보다 작으면 나무를 너무 많이 베고 있다는 뜻이다. 자르는 크기를 줄여야 하므로 범위의 최댓값을 현재의 mid 값으로 재설정한다.

Code

import sys
input = sys.stdin.readline

def main():
	n, m = map(int, input().split())
	tree = sorted(map(int, input().split()))
	left, right = 1, tree[-1]
	mid = right//2
	result = 0
	while mid != left:
		h = [t-mid for t in tree if (t-mid)>0]
		add = sum(h)
		if add == m:
			result = mid
			break
		elif add > m:
			result = mid
			left = mid
			mid = (left+right)//2
		else:
			right = mid
			mid = (left+right)//2
	
	print(result)

main()