Algorithm in A..Z - Binary Search

개념

탐색 범위를 반으로 줄이면서 값을 찾는 방법이다.

---

작동원리

1. 탐색 범위를 정렬한다.

2. l -> 탐색 범위 최소값, r -> 탐색 범위 최대값, m -> 탐색 범위 중간값

3. m에 찾으려는 위치가 있는지 확인한다.

4. m에 찾는 값보다 큰 값이 존재하면 r을 m - 1로 바꾼다. ( 정렬되어있기 때문에 m보다 큰 인덱스에 저장된 값은 m에 저장된 값보다 크기 때문에 확인할 필요가 없다.)

5. m에 찾는 값보다 작은 값이 존재하면 l을 m + 1로 바꾼다. (정렬되어있기 때문에 l보다 작은 인덱스에 저장된 값은 m에 저장된 값보다 작기 때문에 확인할 필요가 없다.)

6. l <= r을 만족하거나 값을 찾을 때까지 3 ~ 4를 반복한다.

---

시간 복잡도

O(logN)

---

문제

2805 나무 자르기

www.acmicpc.net/problem/2805

2805번: 나무 자르기

---

코드

#include <bits/stdc++.h>
using namespace std;

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

    int n, k;
    cin >> n >> k;

    vector<long long> ve(n);
    for (auto &i : ve) {
        cin >> i;
    }

    long long ans;
    long long l = 0, r = *max_element(ve.begin(), ve.end());
    while (l <= r) {
        long long m = (l + r) / 2;

        long long sum = 0;
        for (auto &height : ve) {
            if (height > m) {
                sum += height - m;
            }
        }

        if (sum >= k) {
            ans = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    cout << ans << "\n";
}