[ 백준 ] 2805번 - 나무 자르기 (Python)

기본 정보

• Level: silver 3
• Problem Link: 나무 자르기
• Problem Number: 2805
• My Solution Link: 나의 풀이
• Algorithm I used : 이진탐색(binary search)

문제

• 높이 H로 같은 줄에 있는 나무 동시에 자름
• 높이 H 위의 부분을 가져가게 된다.
• 최소 M미터의 나무를 가져가기 위한 높이 H의 최댓값?

알고리즘

• (1,나무 높이 중 최댓값)을 범위로 이진탐색 진행
• 각 나무 높이 - middle : 가져가게 되는 나무
  • 0 이하이면 가져가는 것 없음.

나의 시도

• 시간 초과가 발생했는데, 언어 설정의 문제였다. (Python3 → PyPy3)
• PyPy란 무엇인가?

# 나무의 수, 가져가려는 나무의 길이
n, m = map(int,input().split())

# 주어진 나무들 높이
trees = list(map(int,input().split()))

left, right = 1, max(trees)

while left <= right:
    middle = (left + right) // 2

    result = 0  # 가져갈 나무 길이
    for tree in trees:
        temp = tree - middle
        if temp > 0:
            result += temp

    if result < m:
        right = middle - 1
    else:
        left = middle + 1

print(right)