[백준] 2805번 : 나무 자르기

문제

 

---

풀이

 

myunji.tistory.com/264?category=1154147

[백준] 1654번 : 랜선 자르기

이 문제랑 풀이가 동일하다. 그러니 딱히 설명하지 않도록 하겠다.

---

소스코드

 

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

using namespace std;

typedef long long ll;

int N, M;
vector<ll> tree;

ll cntTree(ll length) { //총 몇 m의 나무가 나오는지 계산
    ll cnt = 0;

    for (int i = 0; i < tree.size(); i++) {
        ll tmp = tree[i] - length;
        if (tmp > 0)
            cnt += tmp;
    }
    return cnt;
}

ll upperSearch(ll left, ll right) { 
    while (left <= right) {
        ll mid = (left + right) / 2;
        ll trees = cntTree(mid);
        if (trees < M)
            right = mid - 1;
        else if (trees >= M) //else로 처리할 수 있지만 lower랑 비교하기 위해 유지
            left = mid + 1;
    }
    return right;
}

int main() {
    ll input;

    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> input;
        tree.push_back(input);
    }
    sort(tree.begin(), tree.end());

    cout << upperSearch(0, tree[tree.size() - 1]);
}

1654번과 풀이가 동일하기 때문에 소스코드도 거의 유사하다.

다만 1부터 시작하는 1654번과 달리 이 문제는 0부터 시작해야 한다는 것을 잊지 말자.

 

ll cntTree(ll length) { //총 몇 m의 나무가 나오는지 계산
    ll cnt = 0;

    for (int i = 0; i < tree.size(); i++) {
        ll tmp = tree[i] - length;
        if (tmp > 0)
            cnt += tmp;
    }
    return cnt;
}

다른 부분은 mid값에 대해 얻을 수 있는 나무의 총 길이를 계산하는 cntTree 함수 뿐이다.

딱히 어려운 함수는 아니므로 설명하지 않겠다.