[정렬/탐색] 백준 2805 나무 자르기 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2805번: 나무 자르기

 

 

 

2. 문제 풀이

 N개의 나무를 동일한 높이로 잘라서 최소 M 크기의 나무토막을 구하는 문제입니다. 이 때, 나무 높이를 최대로 해서 낭비되는 나무를 줄여야 합니다. 나무 높이를 h로 자를 때, h보다 작은 나무들은 잘라지지 않습니다.

 

2022.02.10 - [Algorithm] - [정렬/탐색] 백준 1654 랜선 자르기 - Python

[정렬/탐색] 백준 1654 랜선 자르기 - Python

 랜선 자르기 문제와 비슷한 문제입니다. 1부터 최대 나무 높이까지 중 적절한 높이를 찾기 위해 '이진 탐색'을 이용합니다.

 

2022.02.09 - [Algorithm] - [Algorithm] 이진탐색(Binary Search), 반반 나누어서 찾자

[Algorithm] 이진탐색(Binary Search), 반반 나누어서 찾자

 이진 탐색에 관련된 설명과 코드는 위에서 보실 수 있습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
tree = list(map(int, input().split()))

start, end = 1, max(tree) # 나무 높이의 최소, 최댓값
# 나무길이를 찾는 이진 탐색
while start <= end:
    mid = (start+end)//2
    wood = 0 #나무토막 총합
    for i in tree:
        if i > mid: # mid 높이보다 클 때만 잘림
            wood += (i-mid) # mid 높이로 잘린 나무토막 길이

    # M보다 나무토막이 많을 경우, 더 길게 자르기
    if wood >= M:
        start = mid + 1
    else: # 나무토막이 부족하면, 더 짧게 자르기
        end = mid - 1
print(end)

 입력받은 나무를 이진탐색하는 게 아닙니다. 1부터 max(tree)까지의 나무 높이를 이진 탐색으로 찾아줍니다. M보다 나무 토막이 많을 경우 더 길게 잘라주고, M보다 나무 토막이 적을 경우 더 짧게 잘라 줍니다.