[BOJ_C++] 2805번 : 나무 자르기

# 문제

 

# 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long low = 0, high = -999, mid, cnt;
    int n, m; cin >> n >>m;
    int* list = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> list[i];
        if (high < list[i]) high = list[i];
    }

    while (low <= high) {
        cnt = 0;
        mid = (low + high) / 2;

        for (int i = 0; i < n; i++) {
            if(list[i]-mid>0)
                cnt += list[i] - mid;
        }

        if (cnt >= m) low = mid + 1;
        else high = mid - 1;
    }

    cout << high;

    return 0;
}

• 이분탐색을 이용하여 low가 high보다 작거나 같을 동안 mid는 (low+high)/2가 되어 각 나무의 길이에서 자를수 있는 나무의 높이가 된다.
• 만약 list[i] - mid의 값이 양수라면 나무를 자르고 난 나머지의 나무 높이를 cnt에 더한다.
• cnt가 주어진 m보다 작거나 같으면 나무의 높이를 더 높이 잡기 위하여 low의 값을 mid + 1로 바꿔주고
• 아니라면 high의 값을 mid - 1로 바꿔준다.
• 최종적으로 결정된 나무 높이를 출력하면 프로그램을 종료한다.

 

# 결과