Life Engineering
[BOJ 2805] 나무 자르기(Python3) 본문
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
N, M=map(int, input().split())
trees=list(map(int, input().split()))
start=1
end=2000000000
result=0
while start<=end:
mid=(start+end)//2
total=0
for tree in trees:
if tree>mid:
total+=(tree-mid)
if total>=M:
result=max(result,mid)
start=mid+1
else:
end=mid-1
print(result)
|
cs |
전형적인 이분탐색 문제
이때 최소값을 0, 최댓값을 트리의 최대 길이로 설정해주어도 ok다. (트리의 최대길이를 넘는 것과 트리의 최대 길이가 절단기가 되었을 때 결괏값은 같다.)
mid 높이로 잘랐을 때 길이가 M 이상이면 오른쪽을 탐색, M 미만이면 왼쪽을 탐색한다.
이때 길이가 M 이상일 때 절단기 값을 result값에 넣어 최대값을 만날 때마다 갱신해준다.
'Problem Solving' 카테고리의 다른 글
[BOJ 5014] 스타트링크 (Python3) (0) | 2021.02.20 |
---|---|
[BOJ 2206] 벽 부수고 이동하기 (Python3) (0) | 2021.02.20 |
[BOJ 1389] 케빈 베이컨의 6단계 법칙 (Python3) (0) | 2021.02.19 |
[BOJ 1931] 회의실 배정 (Python 3) (0) | 2021.02.18 |
[BOJ 6603] 로또 (Python3) (0) | 2021.02.17 |