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

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

문제

---

 송이는 이번 학기에 할 일이 매우 많다. N$N$개의 일 중 어떤 일부터 해야 할지 고민하던 중 송이에게 좋은 아이디어가 떠올랐다! 바로 해야 할 일 각각의 중요도를 산정하고, 중요도가 높은 일부터 하는 것이다. 송이는 하루에 하나의 일만 처리할 수 있으며, 일을 처리한 후 그 일의 중요도는 M$M$만큼 감소한다. 일의 중요도가 K$K$ 이하가 되면 그 일은 완료한 것으로 간주한다. 중요도를 일별로 산정하던 중 송이는 문득 일하면서 본인이 매일 느낄 만족감이 궁금해졌다. 오늘의 만족감은 전날의 만족감을 Y$Y$, 오늘 할 일의 중요도를 P$P$라 할 때 ⌊Y/2⌋+P$\lfloor Y/2 \rfloor+P$와 같다.

예를 들면 다음과 같다. 전날 송이의 만족도가 21$21$이고, 송이가 오늘 할 일의 중요도가 10$10$, M$M$의 값이 4$4$라고 가정했을 때 송이가 오늘 느낄 만족감은 ⌊212⌋+10$\lfloor \frac{21}{2} \rfloor+10$ = 20$20$이 된다. 이후 송이가 오늘 한 일의 중요도는 4$4$만큼 감소해서 6$6$이 된다.

송이가 해야 할 일의 개수 N$N$, 일을 처리했을 때 감소하는 중요도 M$M$, 완료한 것으로 간주하는 중요도의 최댓값 K$K$가 주어진 후, i$i$번 일이 가지는 중요도 Di$D_i$가 입력으로 N$N$개 주어진다. 송이가 모든 일을 끝낼 때까지 며칠이 걸리는지, 그리고 모든 일을 끝낼 때까지 송이가 일별로 느낀 만족감을 한 줄마다 출력하자. 단, 첫날의 경우 전날의 만족감을 0$0$으로 간주한다.

 

입력

---

첫째 줄에 정수 N$N$, M$M$, K$K$가 공백으로 구분되어 주어진다. (2≤N≤2000;1≤M≤5;1≤K≤3)$(2 \leq N \leq 2 \, 000; 1\leq M \leq 5; 1 \leq K \leq 3)$ 

둘째 줄부터 N$N$개의 줄에 걸쳐 해야 하는 일의 중요도 정수 Di$D_i$가 주어진다. (M<Di,K<Di,Di≤1000)$(M< D_i, K < D_i, D_i \leq 1 \, 000)$ 

 

출력

---

첫째 줄에 송이가 일을 다 하기 위해 걸리는 날의 수를 출력한다.

둘째 줄부터 일을 끝내는 날까지 일별로 느낀 만족감을 한 줄씩 구분해 출력한다.

 

문제 풀이

---

우선순위 큐 + 구현 문제.

 

중요도가 가장 높은 일을 그날 하루에 처리하므로, 내림차순 우선순위 큐를 사용해 해당 날짜에 할 일을 선정한다. 일을 처리하고 나면 M만큼 감소시키고, 해당 값이 K보다 크면 다시 다른 날에 일을 또 처리해야 하므로 큐에 넣어준다. 그리고 만족도를 계산해준다. 걸리는 날의 수를 출력해야 하므로 벡터에 날짜별 만족도를 저장하고, 우선순위큐가 빌 때까지 계산한 후 나중에 모든 만족도를 출력해주면 된다.

 

아래는 코드.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M, K, D;
	int satisfaction = 0;
	priority_queue<int, vector<int>, less<int>> pq;
	vector<int> answer;
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
	{
		cin >> D;
		pq.push(D);
	}
	while (!pq.empty())
	{
		int top = pq.top();
		satisfaction = satisfaction/2 + top;
		answer.push_back(satisfaction);
		pq.pop();
		int next = top - M;
		if (next > K)
		{
			pq.push(next);
		}
	}
	cout << answer.size() << "\n";
	for (int i = 0; i < answer.size(); i++)
	{
		cout << answer.at(i) << "\n";
	}
	return 0;
}