BOJ 27279 : 조사전달

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

27279번: 조사전달

---

코드

#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, m;
    cin >> n >> m;

    vector<int> s(n), w(m);
    for(auto & u : s) cin >> u;
    for(auto & u : w) cin >> u;
    sort(all(s));
    sort(all(w));

    bool ans = true;
    int idx = 0;
    for(int i = 0; i < m; i++) {
        while(idx < n && s[idx] < i+1) idx++;
        if(idx >= n) {
            ans = false;
            break;
        }
        while(w[i] && idx < n) {
            w[i]--;
            idx++;
        }

        if(w[i]) {
            ans = false;
            break;
        }
    }

    cout << (ans ? "YES" : "NO");

    return 0;
}

---

풀이

우선 사역의 번호는 풀이에 큰 영향을 주지 않으므로 차출해야 하는 병사의 수를 기준으로 오름차순으로 새롭게 번호를 매겨보자.

병사들이 사역에 지원하는 최악의 경우에 대해 생각해보면 골고루 지원하는 것이 아닌 일부의 사역에 몰려 지원하는 경우일 것이다. 그 중에서도 인원이 적은 사역에 많이 지원하는 경우가 최악일 것이다.

앞에서 번호를 새롭게 매겼으니 최악에 상황에 대해 다르게 정의할 수 있다. 병사가 희망하는 사역의 수가 k일때, 1부터 k번까지의 사역을 희망하는 경우라고 할 수 있다. 이 경우 k+1번 이상의 사역에 대해서는 k개 이하의 사역을 희망하는 병사를 차출할 수 없는 것이다.

 

최악의 상황에 대한 정의를 마쳤으니 이 경우에 대해 최선의 방법을 찾아보자. 어떤 사역에 대해서 차출이 가능한 병사들이 있을 때, 이 중 가능한 적은 양의 사역을 희망하는 병사를 차출하는 것이 이득이다. 또한 이렇게 매 순간마다 이득을 취하는 것이 최선임을 증명할 수 있다.

 

최악의 상황에 대해 최선의 방법으로 배치했을 때 모든 사역의 차출이 가능하면 모든 경우에 대해서 가능하다.