[백준] 2805 나무 자르기 (파이썬 python)

 

 

문제 링크

 

 

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

2805번: 나무 자르기

 

 

 

문제

 

 

 

 

 

문제 풀이

 

 

이분 탐색으로 푸는 문제이다.

시작점을 1, 끝점을 입력받은 len의 최댓값으로 두고 mid를 구하여 len에서 뺀 값을

모두 더하는 것으로 상근이가 얻을 수 있는 길이를 구한다.

이 때, 주의해야 할 점은 나무의 길이가 중간값보다 길 때만 빼야한다는 것이다.

이 조건문을 빼놓으면 마이너스 값도 얻을 수 있는 값을 더할 때 포함되므로

값이 작게 나올 수 있다!

 

# pypy3 제출

import sys

M, N = map(int, sys.stdin.readline().split())
len = list(map(int, sys.stdin.readline().split()))

start, end = 1, max(len)

while start <= end:
    mid = (start + end) // 2
    get = 0
    for i in len:
        if i >= mid:
            get += i - mid
    if get >= N:
        start = mid + 1
    else:
        end = mid - 1

print(end)