백준_2805번

2805번 나무자르기

주어지는 길이의 나무들을 같은 길이로 잘라 원하는 길이의 나무만큼 얻을 수 있다고 했을 때 가장 긴 길이를 구하는 문제.

이전에 풀었던 랜선구하기 문제와 비슷했다.

import sys
input = sys.stdin.readline

n,m = map(int,input().split()) # 나무의 수, 가져가려는 나무의 총 길이
tree = list(map(int,input().split())) # 나무들의 길이 리스트
x,y = 1,max(tree) # 중간 값을 구하기 위한 최소값, 최대값

while x <= y:
    mid = (x+y) // 2 # 중간값
    cnt = 0
    for i in tree:
        if i > mid: # 나무의 길이가 중간 값 보다 클 경우에만
            cnt += (i-mid) # 잘라낸 나무의 길이를 합산
    if cnt >= m: # 만약 잘라낸 나무들의 길이가 원하는 것보다 길면
        x = mid + 1 # 중앙값을 더 큰 수들 중에서 찾음
    elif cnt < m: # 짧으면
        y = mid - 1 # 중앙값을 더 작은 수들 중에서 찾음
print(y)