오늘의 학습 키워드

• 이분탐색 대상과 부등호 찾기
• 이분탐색 [*$start = 0$, $end = \text{max element}$]

[백준] 나무 자르기 - 2805

• [백준] 나무 자르기 - 2805
• Silver II
• C++ 풀이
• 풀이시간: 30m

문제해설

$N$개의 나무에서 각 나무의 높이 $n_i$ 를 기준 높이 $H$만큼 잘랐을 때, 남은 나무의 길이 누적합이 최소 $M$ 미터를 만족하도록 하는 높이 $H$의 최대값을 찾는 문제

접근법: 이분탐색

이분탐색 대상과 부등호

이분탐색의 대상은 출력값인 높이 $H$이다. $H$를 기준으로 나무를 잘라서 남은 나무의 길이 합, 즉 $sumM$이 최소 $M$ 이상이 될 때까지 이분탐색을 진행한다.

#include <bits/stdc++.h>
using namespace std;

int N;
long long M;
long long tree[1000002];

int main(){
    cin >> N >> M;
    for (int i = 0; i < N; i++){
        cin >> tree[i];
    }

    long long st = 0, end = *max_element(tree, tree + N), answer = 0, mid;
    while(st <= end){
        mid = (st + end) / 2;
        long long sumM = 0;
        for (int i = 0; i < N; i++){
            sumM += (tree[i] - min(mid, tree[i]));
        }
        if (sumM >= M) {
            st = mid + 1;
            answer = mid;
        }
        else {
            end = mid - 1;
        }
    }
    cout << answer;
}

오늘의 회고

이 문제는 6개월 전, 이분탐색에 대해 충분히 이해하지 못했을 때 도전했다가 포기한 문제이다. 이번에 문제를 해결하면서 이분탐색에 대해 마스터한 것 같아 정말 뿌듯하다. 👍🏻
문제를 읽다가 헷갈리는 경우가 있는데, start는 왠만해서 $0$으로 초기화하는 것이 맞는 것 같다.