[백준/파이썬(Python)] 나무자르기 2805

🐱문제

---

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

2805번: 나무 자르기

 

🐱풀이

---

벌목 높이를 움직여서 필요 나무 길이를 채우는지 확인한다.

1. 가장 짧은 길이 1을 start로 정하고, 나무 중에 가장 긴 길이를 end로 설정한다.
2. 이진탐색이 끝날 때까지 while문을 돌린다.
3. mid를 start와 end의 중간으로 두고, 모든 값에서 mid를 빼서 총 어느정도 길이의 벌목된 나무가 나오는지 확인한다.
   1. 만약 벌목된 나무가 목표치 이상이면 mid+1을 start로 설정한다.
   2. 만약 벌목된 나무가 목표치 이하이면 mid-1을 end로 설정한다.
4. start=end가 되거나 조건을 만족하는 최대 나무 절단 높이를 찾아서 반환한다.

 

🐱코드

---

n,m=map(int,input().split())
tree=list(map(int,input().split()))
start,end=1,max(tree)

while start<=end:
	mid=(start+end)//2
	total=0
	for t in tree:
		if t>=mid:
			total+=t-mid
	if total>=m:
		start=mid+1
	else:
		end=mid-1
print(end)