[C++] 백준 23254번: 나는 기말고사형 인간이야

문제 링크

23254번: 나는 기말고사형 인간이야

문제 요약

시험 공부를 하는데, 각 과목당 현재 시험을 봤을 때 받을 수 있는 점수, 1시간 공부했을 때 증가하는 점수가 주어진다. 이때 받을 수 있는 점수의 최댓값을 구해야 한다.

접근 방법

그리디하게 접근하였습니다. 점수가 최대가 되야하기 때문에, 매 시간마다 현재 1시간을 투자했을 때 점수의 증가치가 가장 높을 과목에 1시간을 투자하는 식으로 구현을 했습니다. 이러한 사항을 위해서 저는 우선순위큐를 사용하였습니다. 우선순위큐는 (100 - 현재 가능한 점수)와 (1시간 공부해서 증가 가능한 점수) 중 최솟값을 기준으로 내림차순으로 정렬됩니다. 그리고 공부가 가능한 매 시간마다 공부를 해서 점수를 증가시키고 다시 큐에 넣습니다. 만약 100점에 달하면 우선순위큐에서 아예 제거해줍니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct compare
{
	bool operator()(const pair<int, int>& a, const pair<int, int>& b)
	{
		return min(100 - a.first, a.second) < min(100 - b.first, b.second);
	}
};

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;

	vector<pair<int, int>> v(m);

	for (int i = 0; i < m; i++) cin >> v[i].first;
	for (int i = 0; i < m; i++) cin >> v[i].second;

	priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;

	for (auto& i : v) pq.push(i);

	int ans = 0;
	for (int i = 0; i < 24 * n; i++)
	{
		if (pq.empty())
			break;

		auto now = pq.top();
		pq.pop();

		now.first = min(100, now.first + now.second);

		if (now.first == 100)
		{
			ans += 100;
			continue;
		}

		pq.push(now);
	}

	while (!pq.empty())
	{
		ans += pq.top().first;
		pq.pop();
	}

	cout << ans << '\n';
	return 0;
}