(Python/🥈2)백준알고리즘 2805번: 나무 자르기

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

풀이:

import sys

N,M = map(int, (input().split()))    # 나무의 수 N, 필요한 나무의 길이 M
height = list(map(int, input().split())) # 높이
start, end = 1, max(height)			# 시작 과 끝
while start <= end:
    mid = (start + end) // 2		# 중간 값

    count = [tree - mid if tree > mid else 0 for tree in height]
    # count = []
    # for tree in height:
    #     if tree > mid :
    #         count.append(tree - mid)
    #     else:
    #         count.append(0)
    res = sum(count)
    if res >= M:
        start = mid +1
    else:
        end = mid - 1


print(end)

삼항 연산자 / 컴프리핸션 /