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

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

2805번: 나무 자르기

문제 설명:

상근이가 얻으려는 나무의 길이 M , 나무의 수 N

M을 얻기 위해 절단기로 자를 수 있느 나무의 최대 높이값을 구하는 문제

만약 4개의 나무 [20, 15, 10, 17]이 주어질때 7미터 얻으려고 할때 15미터로 설정하고 자르면 [0,0,5,2] 7미터를 얻을 수 있다.

 

이진탐색으로 풀 수 있지만 조금 방법을 바꿔보고 싶었다.

• 나무의 리스트를 역순으로 정렬하고 첫번째 요소를 절단기의 최대높이(limit)라고 가정한다.
• 최대높이로 잘랐을때 절단된 나무길이의 합을 구하고 원하는 길이보다 합이 작으면 요소를 앞으로 옮겨준다.
• 그걸 반복하다보면 절단된 나무길이의 합이 구하고자 하는 길이의 합보다 커질 것이다.
• 이때 그 요소와 앞의 요소를 보내 이진탐색을 시작한다.

def func(lst):
    p = 0
    while True:
        limit = lst[p]
        gather = 0
        for val in lst:
            if limit < val:
                gather += val - limit
        if gather < M:
            p += 1
        elif gather == M:
            return lst[p]
        else:
            return binary_search(lst[p-1], lst[p])

하지만 실패했다..! ㅠ 아마 요소를 더했을때 아예 인덱스를 벋어나는 경우도 있을 것이다.

 

다시 이진탐색으로만 찾아보자

• start = 1로 end 는 주어진 트리 리스트에서 가장 큰 값으로 하자

tree = [4,42,40,26,46]
start, end = 1, max(tree)

 

• mid는 start와 end의 중간값으로 한다.
• 트리의 길이의 합을 구하기 위한 변수도 초기화 해준다.

    mid = (start+end) // 2
    tree_length = 0

 

• 절단기의 최대 높이(mid)를 지정해주었으니 나무길이에서 잘라서 몇개가 나오는지 세어본다.
• 이때 주의점은 최대높이보다 작은것은 잘리지 않으니 절단기 최대높이보다 큰 것만 잘라야 한다.

    for i in tree:
        if mid < i:
            tree_length += i - mid

 

• 잘린 트리의 합이 크면 너무 많이 잘랐기 때문에 최대높이를 높여 다시 반복하도록 한다.
• 합이 작으면 최대높이를 낮춰줘서 다시 반복하도록 한다.

    if tree_length >= M:
        start = mid + 1
    else:
        end = mid - 1
  
  print(end)