문제
만식이네 부대에서는 제설 등의 사역에 차출이 필요한 경우, 조사전달을 진행하여 각 병사가 어떤 사역을 진행할 수 있는지 조사전달 체계에 입력한 뒤, 해당 내용을 통합하여 차출자를 선발한다.
오늘 진행해야 하는 사역은 총 M개이다. 하루 동안 진행되는 사역인 만큼 병사는 최대 하나의 사역에만 차출될 수 있으며, 각 사역에는 여러 명의 병사가 필요할 수도 있다. 이에 N명의 모든 병사들은 M개의 사역에 대한 조사전달을 진행하였고, 각 병사는 적어도 하나의 사역에는 차출이 가능하다고 답했다. 하지만 갑작스럽게 조사전달 체계가 고장 나는 바람에, 각 병사가 가능하다고 답한 사역의 개수만이 체계에 저장되었다.
고장 난 조사전달 체계를 보던 만식이는 체계에 저장된 정보만으로 각 병사들이 어떻게 답변했을지 유추해보고 있었다. 그러던 중, 문득 병사들이 어떻게 답변했더라도 모든 사역에 필요한 인원을 차출하는 방법이 있을지 궁금해졌다. 호기심이 많은 만식이를 위해, 만식이의 궁금증을 해결해 주자!
입력
첫 번째 줄에 조사전달에 응답한 병사의 수 N과 사역의 개수 M이 공백으로 구분되어 주어진다. (1≤M≤N≤100000)
두 번째 줄에 N명의 병사가 가능하다고 답한 사역의 개수 a_i가 공백으로 구분되어 주어진다. (1≤a_i≤M)
세 번째 줄에 M개의 사역에 대해 차출해야 하는 병사의 수 b_i가 공백으로 구분되어 주어진다. (1≤b_i≤N; Σb_i≤N)
출력
병사들이 어떻게 답변했더라도 모든 M개의 사역에 필요한 인원을 차출할 수 있으면 YES, 아니면 NO를 출력한다.
C++ 코드
#include <iostream>
#include <algorithm>
using namespace std;
int deathFromDisease[100001];
int fourStation[100001];
int main() {
int n, m;
cin >> n >> m;
for (int i=0; i<n; i++) {
cin >> deathFromDisease[i];
}
for (int i=0; i<m; i++) {
cin >> fourStation[i];
}
sort(deathFromDisease, deathFromDisease + n, greater<>());
sort(fourStation, fourStation + n, greater<>());
int d = 0, a = m;
bool ssapossible = true;
for (int i=0; i<m; i++) {
for (int j=d; j<d+fourStation[i]; j++) {
if (deathFromDisease[j] < a) {
ssapossible = false;
break;
}
}
d += fourStation[i];
a--;
if (!ssapossible) break;
}
cout << (ssapossible ? "YES" : "NO") << endl;
return 0;
}해설
어떻게든 사역을 피하는 방향으로 조사전달에 응답하는 병사들을 상상하며, 가능한 최악의 경우를 정해 두고 코드를 짠다.
아래의 예제 1을 보자.
| 5 4 1 2 4 3 4 1 1 2 1 |
YES |
가장 중요하게 봐야할 것은 2명이 필요한 사역(fourStation), 즉 3번째 사역이다. 마침 모든 사역이 가능한 병사(deathFromDisease)가 2명이므로, 이 두 명을 선정하면 된다.
이때 가장 최악의 상황은 3개의 사역이 가능한 병사가 3번째 사역만 안 한다고 한 경우일 것이다. 왜냐하면 이 병사가 3번째 사역을 할 수 있다면, 이는 3개의 사역이 가능한 병사와 4개의 사역이 가능한 병사가 뒤바뀐 상황이 되므로 더 많은 선택이 가능하기 때문이다.
즉 이 문제는 입력으로 '1 2 3 / 1 1 1'이 주어지는 문제로 볼 수 있다. 이때 첫 번째 사역을 할 수 있는 유일한 병사가 3번째 병사라 하자. 그러면 다시 입력을 '1 2 / 1 1'이 주어지는 문제로 볼 수 있다. 이렇게 병사와 사역을 정렬하여, 가장 많은 병사가 필요한 사역이 요구하는 병사 수만큼 그 때 남은 사역 개수만큼의 사역이 가능한 병사가 있어야 한다는 것을 체크해가면 된다.
이해가 중심이 되는 그리디 알고리즘 문제였다.