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

Problem

일정 길이로 나무를 자르고 남는 합,
결정 알고리즘의 최적해를 구하는 문제

Solution

이분탐색을 통해 범위설정후 값 탐색

코드설명

1)이분탐색의 범위 설정=>lt=1 rt=트리의 최대길이
2)이분탐색후 잔여값을 구하기
3)잔여값이 목표값보다 크면, 즉 높이를 내려야하면 lt=mid+1,반대는 rt=mid-1

※생각보다 파이썬으로 풀어 그런지 시간에 예민한 문제.

Python Code

import sys

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

arrList=list(map(int,sys.stdin.readline().split()))

lt=1
rt=max(arrList)
result=0

def Count(len):
    cnt=0

    for value in arrList:
        if value>=len:
            cnt+=value-len
    return cnt
while lt<=rt:
    mid=(lt+rt)//2
    res=Count(mid)


    if res>=M:
        lt=mid+1
        result = mid
    else:
        rt=mid-1
print(result)