백준 2805번: 나무 자르기 (Python)

접근

이전 문제인 백준 1654번 랜선 자르기 문제와 매우 유사한 문제였고, 마찬가지로 비슷한 내용의 이분내용의 이분탐색 알고리즘을 이용하여 해결할 수 있었다.

2021.04.05 - [코딩/백준 (Python)] - 백준 1654번: 랜선 자르기 (Python)

백준 1654번: 랜선 자르기 (Python)

절단기가 자를 높이의 최소값, 최대값을 이용하여 최초 범위를 구하고, 이분탐색으로 높이를 탐색해가면서 잘려진 나무들의 길이 합이 목표값보다 커지는 최소값을 탐색하여 문제를 해결할 수 있다.

코드

import sys

n, need = map(int, sys.stdin.readline().split())
trees = list(map(int, sys.stdin.readline().split()))
minh = 0
maxh = max(trees)


def cut(h):
    length = 0
    for i in trees:
        if i > h:
            length += i - h
    return length


def binarysearch(minh, maxh, target):
    midh = (minh + maxh) // 2
    if minh >= maxh - 1:  # 잘려진 나무 길이 합이 목표값보다 커지는 절단기 높이 최대값이 return된다.
        return minh
    if cut(midh) < target:
        return binarysearch(minh, midh, target)
    else:
        return binarysearch(midh, maxh, target)


print(binarysearch(minh, maxh, need))

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!