문제 푼 날짜 : 2021-07-14

문제

문제 링크 : https://www.acmicpc.net/problem/2805

접근 및 풀이

이진 탐색 알고리즘을 적용하면 쉽게 풀 수 있는 문제였다.
나무를 못가져가는 경우는 입력으로 들어오지 않기 때문에, (1 ~ 가장 높은 나무 높이) 범위에서 기준이 되는 절단기 높이를 (1 + 가장 높은 나무 높이)/2 로 정하였다.
이를 기준으로 나무를 절단했을 때 가져가는 높이가 M보다 크거나 같으면서 최대가 되는 절단기 높이를 구해주었다.

코드

// 백준 2805번 : 나무 자르기
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
long long M;
vector<long long> wood;

long long check(long long base) {
    long long sum = 0;
    for (int i = 0; i < wood.size(); i++) {
        if (wood[i] - base <= 0) {
            continue;
        } else {
            sum += wood[i] - base;
        }
    }
    return sum;
}

long long BinarySearch() {
    long long ans = 0;
    long long first = 1, last = wood[N - 1];
    
    while (first <= last) {
        long long mid = (first + last)/2;

        if (check(mid) >= M) {
            ans = max(ans, mid);
            first = mid + 1;
        } else {
            last = mid - 1;
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        long long height;
        cin >> height;
        wood.push_back(height);
    }
    sort(wood.begin(), wood.end());

    cout << BinarySearch() << '\n';
    return 0;
}

결과

피드백

int, long long 선언도 신중하게!