Hikenny25
2805 - 나무 자르기 본문
https://www.acmicpc.net/problem/2805
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = list(map(int, input().split()))
def check(x):
s = 0
for i in range(n):
k = a[i] - x
if k > 0:
s += k
return True if s >= m else False
start = 0
end = max(a)
while start + 1 < end:
mid = (start + end) // 2
if check(mid):
start = mid
else:
end = mid
if check(end):
print(end)
else:
print(start)
- 매개 변수 탐색(이분 탐색)
전 문제인 랜선 자르기랑 비슷한 문제라 어렵지 않게 풀었다
제대로 이해한듯ㅋ
'baekjoon (solved.ac) > class 2 AllSolve' 카테고리의 다른 글
| 18110 - solved.ac (1) | 2023.12.08 |
|---|---|
| 18111 - 마인크래프트 (0) | 2022.10.26 |
| 1654 - 랜선 자르기 (0) | 2022.10.24 |
| 2839 - 설탕 배달 (0) | 2022.10.23 |
| 2869 - 달팽이는 올라가고 싶다 (0) | 2022.10.22 |
'baekjoon (solved.ac)/class 2 AllSolve' Related Articles
more
