BOJ 31410 : 제독 작전

• 문제 링크 : boj.kr/31410
• 난이도 : G3
• 태그 : 그리디, 정렬

31410번: 제독 작전

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n;
    cin >> n;
    vector<pll> arr(n);
    for(auto &u : arr) {
        cin >> u.first >> u.second;
    }
    sort(all(arr));
    ll l = arr[0].second, r = arr[n-1].second;
    ll ans;
    for(int i = 1; i < n; i++) {
        if(i == n-1) ans = l;
        l += arr[i].second;
        l += (i) * (arr[i].first - arr[i-1].first);
    }
    for(int i = n-2; i >= 0; i--) {
        if(i == 0) ans = min(ans, r);
        r += arr[i].second;
        r += (n-1-i) * (arr[i+1].first - arr[i].first);
    }
    for(int i = 0; i < n; i++) {
        ans = min(ans, l - (arr[i].second + arr[n-1].first - arr[i].first));
        ans = min(ans, r - (arr[i].second + arr[i].first - arr[0].first));
    }
    cout << ans;

    return 0;
}

---

풀이

끝에서 끝까지 한 방향으로 이동하며 제독하는 것이 최적임을 알 수 있다.

끝에서 끝까지 이동하는 것을 두 방향으로 나누어 값을 구한다.

구해놓은 값을 이용해 끝까지 이동하며 중간에 어떤 오염물질을 제독하지 않고 그대로 이동하는 경우를 계산한다.

여기서 마지막의 오염물질을 제독하지 않는 경우 이러한 방법으로 구할 수 없기 때문에, 미리 모든 오염물질을 제독하는 경우의 값을 구할 때 구해놓는다.