NYPC 2021 예선 | 근무표 짜기

[문제]

 

사회적 거리 두기를 지키기 위해서 넥슨은 재택근무를 실시하고 있다. 다만, 각 개발자들에게는 반드시 사무실에 출근하는 날수가 지정되어 있다. 매일매일 게임 개발자들은 출근할 수도, 재택 근무할 수도 있지만, 주어진 기간 동안 자신에게 주어진 출근하는 날수만큼 반드시 출근해야 한다. 또한, 매일매일 사무실에는 최대 근무할 수 있는 사람 수의 제한이 있으며, 이보다 많은 사람이 출근해서 일할 수는 없다.

예를 들어, 총 일하는 날이 55일이고, 44명의 개발자들마다 반드시 출근해야 하는 날이 다음과 같이 주어졌다고 하자. 각 개발자는 정해진 출근 날수보다 적거나 많이 출근할 수 없다.

만약 55일 동안 매일 최대 출근할 수 있는 사람 수가 차례로 33, 22, 33, 22, 33이라고 하면 다음과 같이 근무표를 짜면 모든 개발자가 조건을 맞출 수 있다.

모든 개발자들의 출근해야 하는 날수와, 매일 사무실에서 근무할 수 있는 최대 사람 수가 주어졌을 때 이 조건을 만족하게 근무표를 작성하는 프로그램을 작성하시오.

 

 

[입력 형식]

 

첫 줄에는 넥슨에서 일하는 개발자 수를 나타내는 정수 N과 근무하는 날수를 나타내는 정수 K가 공백으로 구분되어 주어진다. (1≤N,K≤100)

둘째 줄에는 N 개의 정수가 공백으로 구분되어 주어지는데, 이는 차례대로 각 개발자가 출근해야 하는 날수를 나타낸다. 이 수들은 모두 0 이상 K 이하이다.

셋째 줄에는 K 개의 정수가 공백으로 구분되어 주어지는데, 이는 차례대로 매일매일 사무실에서 일할 수 있는 사람 수의 최댓값을 나타낸다. 이 수들은 모두 0 이상 N 이하이다.

항상 주어진 조건을 만족하게 근무표를 작성할 수 있도록 입력이 주어진다.

 

 

[출력 형식]

 

총 K 줄로 출력한다.

i번째 줄은 i번째 날의 근무표를 나타낸다. 이 줄의 첫 번째 수 xi​는 i번째 날 근무하는 사람 수를 나타낸다. 다음 xi​ 개의 수를 공백으로 구분하여 출력하는데, 이는 이 날 근무하는 개발자를 나타낸다.

각 개발자는 입력받은 순서대로 1,2,⋯,N으로 표현하는데 유의하라.

만약, 가능한 답이 여러 가지인 경우 그중 아무거나 하나 출력한다.

 

 

[해설]

 

그리디로 해결할 수 있는 문제입니다.

N명의 개발자를 차례대로 확인하면서 K개의 날짜 중에 필요 근무 인원이 가장 많이 남아있는 날을 골라 개발자를 배치해 주면 해결할 수 있습니다.

 

 

[C/C++ 코드]

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 101
int n,k,arr[MAX],brr[MAX];
vector<int>result[MAX];
priority_queue<pair<int,int> >pq;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	for(int i=0;i<k;i++){
		cin>>brr[i];
		pq.push({brr[i],i}); // {day,idx}
	}
	for(int i=0;i<n;i++){
		vector<pair<int,int> >v;
		for(int j=0;j<arr[i];j++){
            result[pq.top().second].push_back(i+1);
            v.push_back(pq.top());
            v.back().first--;
            pq.pop();
		}
		for(auto &w:v){
			pq.push(w);
		}
	}
	for(int i=0;i<k;i++){
        cout<<result[i].size()<<" ";
        for(auto &w:result[i]){
        	cout<<w<<" ";
		}
		cout<<'\n';
	}
}