[백준/BOJ] 13904. 과제 [Gold 3]

13904. 과제

문제출처 : https://www.acmicpc.net/problem/13904

code

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

bool compare(const pair<int,int> &a, const pair<int,int> &b)
{
	if (a.second == b.second)
		return a.first > b.first;
	return a.second > b.second;
}
int main()
{
	ios::sync_with_stdio(false);

	int N, lastday = 0, score = 0;
	cin >> N;
	vector<pair<int, int>> homework(N);

	for (int i = 0; i < N; i++)
	{
		cin >> homework[i].first >> homework[i].second;
		if (lastday < homework[i].first)
			lastday = homework[i].first;
	}
	sort(homework.begin(), homework.end(),compare);

	while (lastday)
	{
		for (int i = 0; i < N; i++)
		{
			if (homework[i].first >= lastday)
			{
				score += homework[i].second;
				homework[i].first = 0;
				homework[i].second = 0;
				break;
			}
		}
		lastday--;
	}

	cout << score;
	return 0;
}

드디어 어제 시험이 끝났다 (교양시험2개남았는데 그러려니한다)
드디어 백준을 풀 여유가 생긴다는 사실이 너무 기분이 좋았다.

이 문제는 오랜만에 vector pair개념이 나왔다.
예전에는 멋도 모르고 compare함수를 복붙해서 쓴적이 한번있는데,
오늘은 compare함수에 대해서 공부를 좀 한것같다.
함수에 < 이면 오름차순으로 정렬을 하는거고 > 이면 내림차순으로 정렬하는거다.

이 문제에서 가장 높은 점수를 얻으려면 하루하루지날 때 마다 그날 할 수 있는 최대한 많은점수를 주는 과제를 하면된다.

즉, 기한이 가장 많이 남은 날짜를 구해서 거꾸로 반복문을 돌면서 그날 할 수 있는 가장 높은 점수의 과제를 하면된다.
그러려면 pair로 묶인 vector를 점수(second)를 기준으로 내림차순으로 정렬하고, 점수가 같으면 기한이 더 많이 남은순(first도 내림차순)으로 정렬하면 위에서부터 순차적으로 내려오기 수월 하다고 생각했다.

거의 3주동안 못해서 머리가 굳을 대로 굳었는데, 긴장감을 불어넣어준 문제였던 것 같다.