# [Gold IV] 조사전달 [문제 링크](https://www.acmicpc.net/problem/27279) ## 문제 설명 <p>만식이네 부대에서는 제설 등의 사역에 차출이 필요한 경우, <strong>조사전달</strong>을 진행하여 각 병사가 어떤 사역을 진행할 수 있는지 조사전달 체계에 입력한 뒤, 해당 내용을 통합하여 차출자를 선발한다.</p> <p>오늘 진행해야 하는 사역은 총 $M$개이다. 하루 동안 진행되는 사역인 만큼 병사는 최대 하나의 사역에만 차출될 수 있으며, 각 사역에는 여러 명의 병사가 필요할 수도 있다. 이에 $N$명의 모든 병사들은 $M$개의 사역에 대한 조사전달을 진행하였고, 각 병사는 적어도 하나의 사역에는 차출이 가능하다고 답했다. 하지만 갑작스럽게 조사전달 체계가 고장 나는 바람에, 각 병사가 가능하다고 답한 사역의 개수만이 체계에 저장되었다.</p> <p>고장 난 조사전달 체계를 보던 만식이는 체계에 저장된 정보만으로 각 병사들이 어떻게 답변했을지 유추해보고 있었다. 그러던 중, 문득 병사들이 어떻게 답변했더라도 모든 사역에 필요한 인원을 차출하는 방법이 있을지 궁금해졌다. 호기심이 많은 만식이를 위해, 만식이의 궁금증을 해결해 주자!</p> ## 입력 <p>첫 번째 줄에 조사전달에 응답한 병사의 수 $N$과 사역의 개수 $M$이 공백으로 구분되어 주어진다. $(1\leq M\leq N\leq 100\,000)$</p> <p>두 번째 줄에 $N$명의 병사가 가능하다고 답한 사역의 개수 $a_i$가 공백으로 구분되어 주어진다. $(1\leq a_i\leq M)$</p> <p>세 번째 줄에 $M$개의 사역에 대해 차출해야 하는 병사의 수 $b_i$가 공백으로 구분되어 주어진다. $(1\leq b_i\leq N;$ $\sum{b_i}\leq N)$</p> ## 출력 <p>병사들이 어떻게 답변했더라도 모든 $M$개의 사역에 필요한 인원을 차출할 수 있으면 <span style="color:#e74c3c;"><code>YES</code></span>, 아니면 <span style="color:#e74c3c;"><code>NO</code></span>를 출력한다.</p> ## 풀이 #### 주어진 상황에서 병사들끼리 가장 많이 겹치는 최악의 상황을 만들고 병사를 최적으로 배치해 가능한지 확인했다. ``` c++ #include<bits/stdc++.h> using namespace std; const int MAX = 100'002; int a[MAX], b[MAX]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=m;i++) cin >> b[i]; sort(&b[1], &b[m+1]); // i는 최대 a[i]번째 깊이의 일까지 할 수 있음. for(int i=1;i<=n;i++) b[a[i]]--; // 그리디하게 배치 못하는 경우 "NO" for(int i=m;i>=1;i--) { if(b[i+1]<0) b[i] += b[i+1]; if(b[i]>0) { cout << "NO"; return 0; } } cout << "YES"; } ```