[백준][Python] 2805 나무 자르기

실버 2 / 이진 탐색

 

🌳

 

https://www.acmicpc.net/problem/2805

 

 

내 풀이

def cutter():
    s = 0
    e = max(trees)
    height = 0

    while s <= e:
        total = 0
        mid = (s + e) // 2
        for i in trees:
            if i > mid:
                total += i - mid

        if total >= M:
            s = mid + 1
            height = mid
        else:
            e = mid - 1

    return height

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

print(cutter())

 

 

코드 설명

 

이진 탐색(이분 탐색) 문제였다.

 

✔️ cutter 함수 내

s = 0
e = max(trees)
height = 0

s: 자를 통나무의 시작 높이

e: 자를 통나무의 끝 높이

height: 자를 통나무의 최종 높이(답) 

 

while s <= e:
    total = 0
    mid = (s + e) // 2
    for i in trees:
        if i > mid:
            total += i - mid

    if total >= M:
        s = mid + 1
        height = mid
    else:
        e = mid - 1

 

시작 높이가 끝 높이보다 작거나 같은 동안 반복하며 이분 탐색을 진행한다.

현재 자를 통나무의 높이(mid) 보다 긴 통나무라면 잘리게 될 높이(i - mid)를 구하여 total에 더해준다.

 

1. 모든 통나무를 자르고 얻은 나무의 길이가 M(필요한 나무의 길이) 보다 크거나 같은 경우

➡ 우선 M 이상의 나무를 얻은 것이니, height에 해당 높이를 저장한다.

➡ 나무를 필요한 만큼만 가져가야 하므로 시작 높이를 늘린다. → s = mid + 1

➡ 즉, 나무가 덜 잘리도록 한다. (조건은 충족했으나, 지금보다 최선의 케이스가 있는지 확인하기 위함)

 

2. 모든 통나무를 자르고 얻은 나무의 길이가 M보다 작은 경우

➡ 무조건 M 이상의 나무를 얻어야 하므로 끝 높이를 줄인다. → e = mid - 1

➡ 즉, 나무가 더 잘리도록 한다.

 

 

⚡️ 참고

 

결국 반복문이 끝나고 나면 e가 정답이 된다.

절단기에 설정할 수 있는 높이의 최댓값을 구하면 되기 때문!

이 부분이 이해가 될 듯 말듯해서 M 이상의 나무를 얻었다면 height에 해당 높이를 저장하는 방식을 통해 직관적으로 코드를 작성하였다.