[백준 2805번] | 나무 자르기 | 이분탐색, 이진탐색, Binary search (파이썬)

2805번: 나무 자르기

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

 

백준 2805번

 

문제 접근

절단기의 최적높이 H를 좁혀나가야 할것같다

최소 M미터는 갖고가야 하므로 H 시작값은 20(가장 긴 나무) - 7(갖고갸아하는 나무)

최대값은 20(가장 긴 나무의 값)으로 두고 이진탐색(binary search)을 하면 될것같다

 

전체 코드

import sys

treeCount, length = map(int,sys.stdin.readline().split())
tree_list = list(map(int,sys.stdin.readline().split()))

set_lenght = max(tree_list[0],tree_list[-1],tree_list[len(tree_list)//2]) - length  # 세개중 최대값(첫,끝,중간중)
if set_lenght < 0 : # 세팅값 음수면
    set_lenght = 0
rt = 1000000000
lt = set_lenght
while (lt<=rt):
    mid = (lt+rt) // 2
    take_sum = 0    
    for i in tree_list:
        if i > mid:  # 절단되는 나무 높이 합
            take_sum += (i - mid)
            
    if take_sum >= length:   # 가져가는 나무 높이 합 > 가져가려 했던 높이 -> 더 잘라도 됨 -> 세팅 높이 더 높게
        lt = mid+1
        set_lenght = mid
    elif take_sum < length: # 덜 잘라야함
        rt = mid-1
        
sys.stdout.write(f"{set_lenght}\n")

 

가장큰 나무를 찾기위해 sort함수 쓰니 시간초과 발생

 

대신 lt = max(처음 나무, 중간 나무, 마지막 나무) - M

rt는 가장 긴 나무 대신 1,000,000,000(입력으로 들어올수 있는 가장 큰 나무길이)으로 설정

 

mid가 절단기 높이 이므로 이를 이용해 절단되는 나무 높이 합을 구한다

나무들의 합 > M 이면 절단기를 더 높혀야 하므로 lt를 변경

나무들의 합 < M 이면 덜 잘라야 하므로 rt를 변경한다

 

정답

 

위는 sort로 인한 시간초과