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

📌문제 출처

솔브닷 3++ 클래스 단계
https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

❓ 문제

📗 풀이 코드

'''
설정하는 높이가 h이고 나무의 높이가 tree일때 상근이가 가져가는 나무 길이 l
l = tree - h if tree > h else 0
h를 0에서 max(trees)까지 이분 탐색하며 전체 나무 길이가 m 이상인 지점을 찾자
똑같은 높이의 나무에 대해서는 여러번 연산해줄 필요없이 개수를 곱해주자(Counter 사용)
'''
from collections import Counter
input = open(0).readline

def solution(m,trees):
    counter = Counter(trees)
    left,right = 0, 1000000000 # 이분 탐색의 시작과 끝
    while left<=right :
        mid = (left+right)//2 # 중간
        # 나무 높이 하나씩을 꺼내서 자른 길이를 더해준다.
        # 이때 하나의 나무 높이에 나무 높이의 개수(counter의 value)를 곱해서 시간 단축
        tmp_m = sum([(key-mid)*value for key,value in counter.items() if key>mid])
        if tmp_m >= m : # 나무 길이가 m이상일때
            left = mid+1
        else : # 나무 길이가 m미만일때
            right = mid-1
    return right # h가 높아지면 전체 길이가 짧아지는데, while 문이 끝날때의 right가 최대로 전체 나무 길이가 m 이상인 지점 

if __name__ == '__main__':
    n,m = map(int,input().split())
    trees = map(int,input().split())
    print(solution(m,trees))