10주차(이진탐색) - [C++]백준2805 나무 자르기

21 May 2022 in Study on Algorithm

백준2805 나무 자르기 링크

문제

예제 입력

---

코드

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

int res, n, m;
vector<int> arr;
//void Binary_Search(int st, int end) {
//
//    if (st > end) return;
//
//    int mid = (st + end) / 2;
//    long long sum = 0;
//    for (int i = 0; i < n; i++) {
//        if (arr[i] > mid)
//            sum += (arr[i] - mid);
//    }
//    if (sum >= m) {
//        if (res < mid) res = mid;
//        Binary_Search(mid + 1, end);
//    }
//    else Binary_Search(st, mid - 1);
//}

void Binary_Search() {
    int st = 0;
    int end = arr[n-1];

    while (st <= end) {
        int mid = (st + end) / 2;
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] > mid)
                sum += (arr[i] - mid);
        }
        if (sum >= m) {
            if (res < mid) res = mid;
            st = mid + 1;
        }
        else end = mid - 1;
    }
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int h;
        cin >> h;
        arr.push_back(h);
    }
    sort(arr.begin(), arr.end());

    //Binary_Search(0, arr[n - 1]);
    Binary_Search();
    cout << res;
}

설명

이 문제는 알맞은 높이의 나무 길이로 자르기 지점을 찾는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector를 사용하여 구현했습니다. 먼저 나무들을 정렬하여 0~제일 높은 길이 사이에서 최적인 지점을 찾아야 하는데 적은 횟수로 하기위해서 중간 지점부터 확인하며 원하는 값에 점점 가까워지며 더이상 확인할 범위가 없으면 결과를 출력합니다.

<algorithm>
-sort(시작, 끝, 비교함수) : 배열의 크기만큼 정렬

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

---

결과