[알고리즘]나무 자르기(백준 2905/파이썬)

개념:이분탐색

 

이분탐색이란?

데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘입니다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 주어진 A와 비교합니다. A가 중간 값보다 작으면 임의의 값의 좌측의 데이터들을 대상으로, A가 중간값보다 크면 우측을 대상으로 다시 탐색합니다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교하는 방식으로 값을 구하는 방식입니다.

 

 

 

[문제해결방법]

길이가 7인 나무를 구하는데 나무가 잘라져도 상관이 없으니 길이만 맞추면 된다.

그러면 가장 긴 나무부터 나무들의 길이를 잘라 가면서 남은 나무들의 길이를 확인하면 된다.

 

[코드리뷰]

import sys
n,m = map(int,sys.stdin.readline().split())
h = list(map(int, sys.stdin.readline().split()))
# start(L), mid , end(R) := 톱의 높이
L = 0
R = max(h)
#h에서 길이가 가장 긴 나무의 길이 값을 가져 온다
max_mid=0

h.sort(reverse = True)

while L <= R:
    tree=0
    mid = (L+R)//2
    #적절한 나무 값을 찾기 위해서 길이의 중간 값을 구한다
    for i in range(n):
        if mid < h[i]:
            tree += h[i] - mid
            if tree > m :
                break
    if m <= tree :
        if m == tree :
            max_mid=mid
            break
        else :
            L = mid+1
            if mid > max_mid:
                max_mid=mid
    else:
        if m == tree :
            max_mid=mid
            break
        else :
            R = mid-1

[결과]