백준 3195 - ribari (C++)

문제 정보

• https://www.acmicpc.net/problem/3195
• 매개변수 탐색

---

문제 정리

수직선 위에 $N$개의 마을이 있다. 이 마을들은 $B_i$톤만큼의 물고기가 남기 때문에 각 마을마다 $K$명씩 아이들을 데려와 남는 물고기를 먹이려고 한다. 아이 1명은 1년에 1톤의 물고기를 먹는다. 어떤 마을은 물고기가 남고, 어떤 마을은 물고기가 부족할 수 있다. 물고기가 많은 마을에서는 다른 마을로 물고기를 보낼 수 있지만, 물고기를 이동시키면 거리 1당 1톤의 물고기를 세금으로 내야 한다. 모든 마을에서 아이들을 먹일 수 있도록 할 수 있는 최대 K값을 구해야 한다.

---

풀이

문제를 보자마자 K값에 따라 나오는 결정 문제가 TT...TTFF...FF 형태라 매개변수 탐색으로 T의 최대값을 구하는 문제라는 것을 깨달았다.

1. 이분 탐색 진행.
   • "각 마을마다 i명의 아이를 받을 경우 모든 아이들을 먹일 수 있는가?" 를 결정 문제로 잡고 [0, 10^9]의 범위에서 이분 탐색을 진행한다.
2. 결정 문제 처리.
   • 현재 마을의 물고기 수는 (이전 마을까지의 물고기 누적 합) + (이전 마을 -> 현재 마을 이동 세금) + (현재 마을의 아이들이 먹는 물고기)가 된다. 이 중 세금은 두 가지 경우로 나뉜다.
   • 첫 번째 경우는 이전 마을에서 물고기가 남았으나 현재 마을로 이동하는 중 세금을 내며 0이 되버린 경우. 이 경우는 이전까지의 누적 물고기 수가 양수였지만, 현재 마을에서 물고기 수가 음수가 되어버리므로 0으로 바꿔줘야 한다.
   • 두 번째 경우는 이전 마을에서 물고기가 남았고 현재 마을에 도착해도 남아 있는 경우, 또는 이전 마을부터 물고기가 부족했던 경우이다. 이 경우 그냥 세금을 누적 물고기에서 차감해주면 된다.
   • 모든 마을에 대해 위 과정을 처리한 뒤, 남은 물고기가 0 이상이면 아이들을 전부 먹일 수 있는 경우이므로 true를 반환한다.

---

후기

매개변수 탐색인 것을 깨닫는 것은 어렵지 않았는데, 결정 문제 처리가 꽤 어려웠다. G3~G2 사이의 어딘가인듯...

---

코드

// 백준 3195

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>

pii town[100001];


bool check(int N, int v) {
    ll accSum = town[0].second - v;
    for (int i=1; i<N; i++) {
        ll dist = town[i].first - town[i-1].first;

        // 현재 마을로 이동하다 사라져 버리는 경우
        if (accSum >= 0)
            accSum = max(0LL, accSum - dist);
        else
            accSum -= dist;

        // 현재 마을의 사람 수만큼 차감
        accSum += town[i].second - v;
    }

    return accSum >= 0;
}


int solve(int N) {
    // 매개변수 탐색 진행
    int yes = 0;
    int no = 1000000000;

    while (abs(yes-no) > 1) {
        int mid = (yes+no)/2;
        if (check(N, mid) == true)
            yes = mid;
        else
            no = mid;
    }
    return yes;
}


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

    int N;
    cin >> N;
    for (int i=0; i<N; i++) {
        int a, b;
        cin >> a >> b;
        town[i] = {a, b};
    }

    cout << solve(N) << "\n";
}