Algorithm (PS)

[백준] 2805번: 나무자르기 Python - 이진탐색

minjiwoo 2022. 12. 31. 13:20
728x90

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

 

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net

이진탐색으로 높이 H 값을 빠르게 찾는 문제이다. 

백준 1654번 랜선자르기와 풀이방법이 유사하다 ~

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

 

1654번: 랜선 자르기

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그

www.acmicpc.net

n, m = map(int, input().split())
data = list(map(int, input().split()))
start = 0
end = max(data)

while start <= end:
    mid = (start+end)//2
    total = 0
    for i in data:
        if i >= mid:
            total += (i - mid)
    if total < m:
        end = mid-1
    else:
        start = mid+1
print(end)
728x90