(BOJ)-2805, Python

문제 요약

출처: (BOJ)2805 - 나무 자르기

$N$개의 나무와 벌목해야 할 나무의 양 $M$미터가 주어진다. 각 나무의 높이가 주어질 때, 절단기를 이용해 나무를 잘라 최소한 $M$미터 이상의 나무를 얻으려 한다. 이때, 절단기에 설정할 수 있는 최대 높이를 구하는 문제이다.

절단기에 설정할 수 있는 높이는 음이 아닌 정수이다.
나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다.

접근 과정

1. 이분탐색 접근(투 포인터)

이전 포스트에서 다룬 이분 탐색을 적용했다. 필요한 것은 기준에 맞는 절단기 높이를 찾는 것이므로, 0부터 가장 높은 나무의 높이까지 범위를 설정해 탐색하면 될 것이라 생각했다.

완전 탐색으로도 접근할 수 있지만, 시간 초과를 고려해 이분 탐색을 선택했다. 이 문제는 이분 탐색 자체는 쉽게 구현할 수 있지만, “최소한 $M$미터 이상” 이라는 조건을 코드로 구현하는 것에 조금 시간이 걸렸다. 아래는 구현한 코드이다.

코드 구현

##pypy3 제출
N, M = map(int, input().split())
tree = list(map(int, input().split()))
answer = []

s_h = 0
e_h = max(tree)

while s_h <= e_h:
    
    m_h = (s_h + e_h) // 2
    
    sum = 0
    for t in tree:
        if t > m_h:
            sum += t - m_h
    
    if sum == M:
        answer.append([sum, m_h])
        break
    
    if sum > M: #벌목한 양이 초과했으면 절단기를 올려야겠지
        s_h = m_h + 1
        answer.append([sum, m_h])
        continue
        
    if sum < M: #벌목한 양이 부족했으면 절단기를 내려야겠지
        e_h = m_h - 1
        continue
        
print(min(answer, key= lambda x : x[0])[1])

회고

문제의 난이도가 높아질수록 조건을 구현하는 것이 점점 까다로워지는 것 같다. 그래도 차분하게 생각하면서 접근해야겠다.