[C++] 백준 13904번 과제

그리디 알고리즘

과제를 수행해서 가장 많은 점수를 얻는 문제입니다.

점수를 기준으로 오름차순해서 가장 큰 수부터 마감일에 가깝게 넣어줍니다.
들어갈 곳이 없으면 넘어가고 이를 반복해서 들어간 값들을 전부 더해줘서 출력해줍니다.

 

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

int main(int argc, char *argv[]) 
{
	int n;
	int deadline;
	int score;
	int end;
	int result = 0;
	int arr[1001];
	vector<pair<int, int> > v;

	memset(arr, 0, sizeof(arr));

	cin >> n;

	for (int i = 0; i < n; ++i) {
		cin >> deadline >> score;
		v.push_back({ score, deadline });
	}

	sort(v.begin(), v.end(), greater<pair<int, int> >());

	for (int i = 0; i < n; ++i) {
		end = v[i].second;
		while (end >= 1) {
			if (arr[end] == 0) {
				arr[end] = v[i].first;
				break;
			}
			else {
				--end;
			}
		}
	}

	for (int i = 1; i <= 1000; i++) {
		result += arr[i];
	}

	cout << result << endl;

	return 0;
}