no.2805 나무 자르기

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long M;
    cin >> N >> M;

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

    sort(tree.begin(), tree.end());

    long long left = 0;
    long long right = tree[N - 1]; 

    long long result = 0;

    while (left <= right) {
        long long mid = (left + right) / 2;

        long long sum = 0;
        for (int i = 0; i < N; i++) {
            if (tree[i] > mid) {
                sum += tree[i] - mid;
            }
        }

        if (sum < M) {
            right = mid - 1;
        }
        else {
            result = mid;
            left = mid + 1;
        }
    }

    cout << result << "\n";
    return 0;
}

문제분석

나무의 수 N과 집으로 가져가려는 나무의 길이 M이 주어졌을때 

나무를 몇 m로 잘라서 남은 부분을 가져가면 M을 충족하는지 맞추는 문제이다 

간단한 문제인데 

맨처음에는 dp, 즉 브루스포스 방식으로 풀려했으나 

그럴경우 범위가 0부터 최대 10억 에 이를 수있다 

dp를 시도할 경우 보통 dp 테이블 등을 구성해야하는데 

이 문제의 시간 제한은 1초 

즉 dp로 구하면 O(N x 10^9) 의 시간이 걸림 

 

또한 맨처음에 int로 풀었다가 에러가 나서 당황했는데 

이는 tree[i]가 아주 클때 오버플로우 문제가 발생할 수 있기 때문이다. 

최악의 경우 나무 높이가 전부 10^9이고 N=10^6이면

모든 나무를 잘랐을 때 합은 10^15승까지 가기때문에 int의 범위를 초과한다 

 

해결방법은 아주 간단한데, sum 변수를 long long 으로 바꿔주면 된다.