문제
접근
문제 자체는 간단하다.
나무의 높이를 가지고 이분탐색을 진행하면 된다.
높이 보다 큰 값에 대해 어짜피 연산을 진행해야 하므로(높이만큼 잘라야한다) 정렬하는데 걸리는 시간이 더 걸릴 것 같아서 따로 정렬은 진행하지 않았다.
문제를 정의하기가 조금 까다로웠다.
기존 이분 탐색 문제는 뭔가 딱 비례관계를 가지고 있어서, 탐색하는 값을 기준으로 대소 비교를 하면 되었지만,
이 문제는 탐색하려는 높이와 얻을 수 있는 나무의 길이가 반비례 관계를 가진다.
이 부분만 주의하면 된다.
아직도 같거나 작은 값, 혹은 같거나 큰 값을 구하는게 조금 햇갈린다.. 더 많이 구현해봐야 할 것 같다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def cutTreeCalc(arr, h):
s = 0
for item in arr:
if h < item:
s += (item - h)
return s
def binary_search_for_lower_bound(arr, m):
start = 0
end = max(arr)
while start <= end:
mid = (start+end)//2
ans = cutTreeCalc(arr, mid)
if ans < m:
end = mid - 1
elif ans > m:
start = mid + 1
else:
return mid
return end
if __name__ == "__main__":
n, m = map(int, input().split())
arr = list(map(int, input().split()))
ans = binary_search_for_lower_bound(arr, m)
print(ans)