[백준 2805] 나무 자르기 - python (solved.ac - 실버 3)

풀이

문제를 보았을때 알수있는 힌트

나무 m미터가 필요, n개의 나무가 있으며 최대 높이의 나무를 남기고 m미터의 나무를 가져가게 해야함.

최대의 길이인 것을 보아 이진탐색 문제일 것으로 보인다.

 

이를 해결하기위해서 시작,끝,중간을 정해서 나무의 길이를 줄이는 형식으로 진행한다.

 

import sys

input = sys.stdin.readline

n,m = map(int,input().split())
trees=list(map(int,input().split()))
# print(trees)
trees_max = max(trees)
trees_min = 1

while trees_max >= trees_min:
    mid=(trees_max+trees_min)//2
    line=0
    for i in trees:
        line += max(0,i-mid)
    if line>=m:
        trees_min=mid+1
    else:
        trees_max=mid-1
print(trees_max)

문제는 파이썬에서는 해결이 안되서 pypy3를 통해 문제를 해결하였다.

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon2805.py