https://www.acmicpc.net/problem/2805
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
계속되는 이분 탐색 시리즈. 이와 비슷한 류의 문제는 같은 방식으로 작성하는 연습을 하고 있다.
나무를 잘라보자
N, M = map(int, input().split())
trees = list(map(int,input().split()))
lo = 0
hi = max(trees)
mid = (lo+ hi) //2
def is_possible(mid):
tmp = 0
for t in trees:
if t > mid:
tmp += (t-mid)
#print(tmp)
return tmp >= M
ans = 0
while lo <= hi:
#print(lo, mid, hi)
if is_possible(mid):
lo = mid + 1
ans = mid
else:
hi = mid -1
mid = (lo+ hi) //2
print(ans)'ALGORITHM > BOJ' 카테고리의 다른 글
| 11663-선분 위의 점 (0) | 2022.05.03 |
|---|---|
| 1654-랜선 자르기 (0) | 2022.05.02 |
| 10815-숫자카드 (0) | 2022.04.30 |
| 2512-예산 (0) | 2022.04.29 |
| 14502-연구소 (2) | 2022.04.27 |
