개요

이 문서는 이분 탐색을 활용한 알고리즘 문제 해결 과정에 대한 검토를 다룹니다. 각 문제는 이분 탐색과 보조 함수인 check를 결합하여 최적해를 도출하는 전략을 사용합니다. 아래에서는 각 문제에 대한 접근 방식, 오류 원인, 그리고 최종 정답 코드를 재구성하여 설명합니다.

문제 1: 나무 자르기 (P1873)

주어진 높이 이상의 나무를 잘랐을 때 얻을 수 있는 나무 길이의 합이 목표치 이상인지 판단해야 합니다. 이분 탐색의 대상은 절단 높이이며, check 함수는 해당 높이에서 확보할 수 있는 나무의 총량을 계산합니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

bool canHarvest(const vector<ll>& trees, ll H, ll target) {
    ll total = 0;
    for (ll height : trees) {
        if (height > H) total += height - H;
    }
    return total >= target;
}

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

    int n; ll m;
    cin >> n >> m;
    vector<ll> trees(n);
    ll maxH = 0;
    for (int i = 0; i < n; ++i) {
        cin >> trees[i];
        maxH = max(maxH, trees[i]);
    }

    ll left = 0, right = maxH + 1;
    while (left + 1 < right) {
        ll mid = (left + right) / 2;
        if (canHarvest(trees, mid, m)) {
            left = mid;
        } else {
            right = mid;
        }
    }
    cout << left << '\n';
    return 0;
}

문제 2: 목재 구매 (B3880)

공급업체로부터 생성된 나무 조각들을 이용해 최대한 많은 조각을 확보해야 하며, 이때 각 조각의 길이가 일정 값 이상일 경우 분할하여 사용 가능합니다. 입력 처리 시 반복 횟수 실수로 인해 오답이 발생했으며, 이를 n으로 수정함으로써 해결되었습니다.

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
typedef long long ll;

bool enoughPieces(const vector<ll>& len, const vector<ll>& cnt, ll pieceLen, ll required) {
    ll total = 0;
    for (int i = 0; i < len.size(); ++i) {
        total += (len[i] / pieceLen) * cnt[i];
        if (total >= required) return true;
    }
    return false;
}

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

    int n; ll m, l1, s1;
    cin >> n >> m >> l1 >> s1;

    vector<ll> lengths(n), supplies(n);
    lengths[0] = l1; supplies[0] = s1;
    ll maxLen = l1;

    for (int i = 1; i < n; ++i) {
        lengths[i] = ((lengths[i-1] * 37011 + 10193) % 10000) + 1;
        supplies[i] = ((supplies[i-1] * 73011 + 24793) % 100) + 1;
        maxLen = max(maxLen, lengths[i]);
    }

    ll low = 0, high = maxLen + 1;
    while (low + 1 < high) {
        ll mid = (low + high) / 2;
        if (enoughPieces(lengths, supplies, mid, m)) {
            low = mid;
        } else {
            high = mid;
        }
    }
    cout << low << '\n';
    return 0;
}

문제 3: 수열 분할 최적화 (P1182)

배열을 최대 M개의 구간으로 나누되, 각 구간의 합의 최댓값을 최소화해야 합니다. 이분 탐색 범위는 가장 큰 원소부터 전체 합까지 설정하며, check 함수는 주어진 제한 내에서 몇 개의 구간이 필요한지 계산합니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

bool feasible(const vector<ll>& arr, ll limit, int maxSegs) {
    int segments = 1;
    ll currentSum = 0;
    for (ll val : arr) {
        if (currentSum + val <= limit) {
            currentSum += val;
        } else {
            ++segments;
            currentSum = val;
        }
    }
    return segments <= maxSegs;
}

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

    int n, m;
    cin >> n >> m;
    vector<ll> a(n);
    ll maxVal = 0, total = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        maxVal = max(maxVal, a[i]);
        total += a[i];
    }

    ll left = maxVal - 1, right = total + 1;
    while (left + 1 < right) {
        ll mid = (left + right) / 2;
        if (feasible(a, mid, m)) {
            right = mid;
        } else {
            left = mid;
        }
    }
    cout << right << '\n';
    return 0;
}

문제 4: 아이스크림 막대 교환 (B3629)

3개의 막대를 모으면 새로운 아이스크림을 받을 수 있을 때, 최소한 몇 개를 구매해야 N개를 소비할 수 있는지를 구합니다. 이분 탐색을 통해 초기 구매 수를 결정하고, check 함수는 전체 획득 가능한 수량을 시뮬레이션합니다.

#include <iostream>
using namespace std;
typedef long long ll;

bool canConsume(ll initial, ll target) {
    ll total = initial;
    ll wrappers = initial;
    while (wrappers >= 3) {
        ll newIceCreams = wrappers / 3;
        total += newIceCreams;
        wrappers = wrappers % 3 + newIceCreams;
    }
    return total >= target;
}

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

    ll n;
    cin >> n;

    ll low = 0, high = n;
    while (low + 1 < high) {
        ll mid = (low + high) / 2;
        if (canConsume(mid, n)) {
            high = mid;
        } else {
            low = mid;
        }
    }
    cout << high << '\n';
    return 0;
}

문제 5: 돌 건너뛰기 (P2678)

돌 사이의 최소 거리를 최대화하면서 M개 이하의 돌을 제거할 수 있는지를 판단해야 합니다. check 함수는 현재 후보 거리에서 몇 개의 돌을 제거해야 하는지 세며, 이를 바탕으로 이분 탐색을 수행합니다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

bool removableStones(const vector<ll>& rocks, ll minDist, int maxRemove, ll totalLength) {
    int removed = 0;
    ll lastPos = 0;
    for (ll rock : rocks) {
        if (rock - lastPos < minDist) {
            ++removed;
        } else {
            lastPos = rock;
        }
    }
    if (totalLength - lastPos < minDist) ++removed;
    return removed <= maxRemove;
}

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

    ll L; int n, m;
    cin >> L >> n >> m;
    vector<ll> stones(n);
    for (int i = 0; i < n; ++i) {
        cin >> stones[i];
    }

    ll left = 0, right = L + 1;
    while (left + 1 < right) {
        ll mid = (left + right) / 2;
        if (removableStones(stones, mid, m, L)) {
            left = mid;
        } else {
            right = mid;
        }
    }
    cout << left << '\n';
    return 0;
}

문제 6: 옷 건조 문제 (P1843)

건조기에 의한 직접 건조와 자연 건조를 병행할 때 모든 옷을 완전히 말릴 수 있는 최소 시간을 구합니다. 이분 탐색 범위는 넉넉하게 설정하며, check 함수는 남은 습기를 보조 건조로 얼마나 많이 메워야 하는지를 평가합니다.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;

bool canDryAll(const vector<ll>& wetness, ll time, ll dryerPower, ll naturalRate) {
    ll neededAssist = 0;
    for (ll moisture : wetness) {
        ll remaining = moisture - naturalRate * time;
        if (remaining > 0) {
            neededAssist += ceil(remaining / (double)dryerPower);
        }
    }
    return neededAssist <= time;
}

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

    int n; ll a, b;
    cin >> n >> a >> b;
    vector<ll> clothes(n);
    for (int i = 0; i < n; ++i) {
        cin >> clothes[i];
    }

    ll low = 0, high = 25000001;
    while (low + 1 < high) {
        ll mid = (low + high) / 2;
        if (canDryAll(clothes, mid, a, b)) {
            high = mid;
        } else {
            low = mid;
        }
    }
    cout << high << '\n';
    return 0;
}