BOJ 2085 나무자르기

문제

코드 1.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char const *argv[])
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n;
    long long m, num;

    cin >> n >> m;
    vector<long long> v;
    long long top = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> num;
        if (num > top)
        {
            top = num;
        }
        v.push_back(num);
    }
    long long bottom = 1;
    long long tree = 0;
    while (bottom <= top)
    {
        long long mid = (bottom + top) / 2;

        long long length = 0;

        for (int i = 0; i < v.size(); i++)
        {
            long long temp = v[i] - mid;
            if (temp > 0)
                length += temp;
        }

        if (length >= m)
        {
            tree = max(tree, mid);
            bottom = mid + 1;
        }
        else if (length < m)
        {
            top = mid - 1;
        }
    }

    cout << tree << endl;

    return 0;
}

• 가장 긴 나무의 길이를 기준으로 m과 같은 값이 될때 tree 값을 받아 출력하였다.

코드 2

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int MAX = 1000000;
long long tree[MAX];
int N;
long long M;
bool possible(long long height)
{
    long long len = 0;
    for (int i = 0; i < N; i++)
    {
        if (tree[i] - height > 0)
            len += tree[i] - height;
    }
    if (len >= M)
        return true;
    return false;
}
int main(int argc, char const *argv[])
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n, m, num, right = 0;

    cin >> N >> M;
    long long low = 1, high = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> tree[i];

        high = max(high, tree[i]);
    }

    long long result = 0;

    while (low <= high)
    {
        long long mid = (low + high) / 2;
        if (possible(mid))
        {

            result = max(result, mid);
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }

    cout << result << '\n';

    return 0;
}