[코딩테스트 공부] 나무 자르기

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

문제 풀이에 앞서 문제를 분석해봅시다

일단 시간 제한은 1초이고, N은 100만까지 허용이 되어있는 상태입니다. 당연하게도 O(N^2)의 복잡도를 가지게 알고리즘을 구현하면 실패합니다. 따라서 이분탐색을 이용하여 문제를 해결해야합니다.

어떻게 풀어야할까요..?

우리가 구하고자 하는 바부터 확실하게 하고 갑시다. 우리가 구해야하는 것은, 상근이가 적어도 M의 길이만큼 목재를 가져갈 수 있도록 하는 톱날의 최대 높이를 구하는게 관건입니다. 따라서, 이분탐색의 기준을 톱날의 길이에 맞춰서 알고리즘을 설계하면 충분할 듯 합니다.

일단 코드부터 확인해봅시다!

import sys

input = sys.stdin.readline

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

height_list = list(map(int, input().split()))

start = 1
end = max(height_list)

while start <= end:
    mid = (start + end) // 2
    sum = 0
    
    for tree_height in height_list:
        tmp = 0 if tree_height <= mid else tree_height - mid
        sum += tmp
        
    if sum >= M:
        start = mid + 1
    else:
        end = mid - 1

print(end)

이진탐색의 취지에 맞게, mid에 따라서 start, mid의 값을 변경시키면서 범위를 좁히도록합니다!

그리고, 해당 mid의 값에 따라서 나무를 계속 잘라나가는데, 상식적으로 톱날의 높이가 나무의 높이보다 높거나 같은 경우에는 나무가 잘리지 않기 때문에 0을 더하고, 아닌 경우에는 나무의 높이에서 mid 만큼 빼서 sum에 반영해주면 됩니다. 반박시 초능력자

그리고 만일 sum이 원하는 길이보다 컸을 경우에는, 높이를 더 높여도 된다는 뜻이기 때문에 start를 조절하고, 아닌 경우에는 높이를 낮춰야한다는 뜻이므로 end를 조절합니다.

마지막으로, end를 출력해주면 문제는 해결됩니다.