[백준/C++] 31860 열심히 일하는 중

https://www.acmicpc.net/problem/31860

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	int n, m, today, k;
	priority_queue<int, vector<int>> pq;
	queue<int>satisfaction;
	satisfaction.push(0);
 
	cin >> n >> m >> k;
	for (int i = 0, d; i < n; i++) {
		cin >> d;
		pq.push(d);
	}
 
	while (!pq.empty()) {
		today = pq.top();
		pq.pop();
		satisfaction.push(today + satisfaction.back() / 2);
		today -= m;
		if (today > k) pq.push(today);
	}
 
	satisfaction.pop();
	cout << satisfaction.size()<< "\n";
 
	while (!satisfaction.empty()) {
		cout << satisfaction.front() << "\n";
		satisfaction.pop();
	}
	return 0;
}

설명

할 일이 많고 일별 중요도가 크기 때문에 매번 정렬을 해서 풀면 시간초과가 난다. 따라서 우선순위 큐를 이용해서 문제를 푼다.

 

할 일의 개수 n, 감소하는 중요도 M, 완료한 것으로 간주하는 중요도의 최댓값 K를 입력받고, n개의 중요도를 입력받는다. 이때 중요도는 입력받으면서 바로 우선순위 큐에 넣어준다. 이후 우선순위 큐가 빌 때까지 반복문을 돌면서 일을 처리하면 된다. 현재 중요도가 가장 큰 일을 뽑아내고 만족도를 구한 뒤 중요도를 m만큼 감소시킨다. 이때 k보다 클 때만 다시 우선순위 큐에 값을 넣어준다.

 

일을 다 하기 위해 걸리는 날의 수는 만족도 원소 수와 같으므로 이를 출력해주고, 반복문을 돌면서 만족도를 출력해주면 된다.

느낀 점

해당 문제는 제4회 숙명여자대학교 프로그래밍 경진대회 SMUPC B번 문제로, 내가 출제한 문제다. 평소에 내가 문제를 출제하게 된다면 우선순위 큐 문제를 만들어보고 싶다고 생각했었는데, 이번에 출제하게 되어 바로 우선순위 큐를 이용한 문제를 만들었다. 우선순위 큐를 어떻게 문제로 풀어낼지 고민을 했었는데 학교에서 운영체제 수업을 듣다가 해결했다. 스케줄링 파트에서 아이디어를 얻었고 이를 바탕으로 해서 지문을 작성했다.

 

나는 우선순위 큐를 쓸 것을 의도하고 만든 문제이지만, 사용하지 않고도 문제를 통과할 수 있도록 했다. 다만 매번 정렬해서 나이브하게 풀면 시간초과가 나길 의도했기 때문에 시간 제한을 검수진 분들의 피드백을 통해 조정했다!