[백준] 2109 순회강연

[백준] 2109 순회강연

• https://www.acmicpc.net/problem/2109

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

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

	int n;
	cin >> n;

	//<강연 마감일, 강연료>
	vector<pair<int, int>> vec;
	//가장 마지막 강연 마감일 저장
	int maxd = -1;

	for (int i = 0; i < n; ++i) {
		int p, d;
		cin >> p >> d;

		maxd = max(maxd, d);
		vec.push_back({ d, p });
	}

	//가장 마지막 강연 마감일부터 최대 수입 계산
	int income = 0;

	//강의 선택할 수 있는지 여부 저장
	//이미 선택한 강의인 경우 false
	vector<bool> valid(n, true);

	int time = maxd;
	while (time > 0) {
		//현재 강의할 수 있는 강연들 중 가장 강연료 높은 것 선택
		int maxp = -1;
		int maxpIdx = 0;

		//선택할 수 있는 강연이 있는가
		bool flag = false;
		for (int i = 0; i < n; ++i) {
			//강연 마감일 확인
			//이미 마감일 지난 강연 선택할 수 없음
			if (vec[i].first < time) continue;
			
			//이미 선택된 강연 선택할 수 없음
			if (!valid[i]) continue;

			//가장 강연료 높은 강의 찾기
			if (vec[i].second > maxp) {
				maxp = vec[i].second;
				maxpIdx = i;
				
				flag = true;
			}
		}
		if (flag) {
			//가장 강연료 높은 강의 선택
			income += maxp;
			valid[maxpIdx] = false;
		}

		time--;
	}

	cout << income;
	return 0;
}