백준2865 - 나는 위대한 슈퍼스타K

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

2865번: 나는 위대한 슈퍼스타K

그리디 문제다. 점수가 큰 순서대로 정렬을 한 뒤 이미 뽑았던 사람의 점수는 다시 더하지 않고 뽑지 않았던 사람이 었다면 점수를 더한다. 그렇게 되면 큰 순서부터 점수가 더해지기 때문에 결과적으로 뽑고 싶은 사람을 다 뽑았을 때 점수 결과가 가장 크다.

 

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

//compare는 sort의 기준, 점수가 큰 기준으로 정렬한다.
bool compare(pair<int, double> p1, pair<int, double> p2) {
	return p1.second > p2.second;
}

int main() {
	int N, M, K; //N명의 사람, M개의 장르, K는 뽑을 사람의 수
	int people; //사람의 번호
	int cnt = 0; //몇 명의 사람을 골랐는지 기억
	double score; //장르별 점수
	double sum = 0; //뽑은 사람들의 점수 합
	vector<pair<int, double>> v; //사람에 따른 점수를 저장할 공간
	set<int> st; //뽑은 사람의 번호를 저장할 공간

	//참가한 사람의 수 N, 평가할 장르 M, 뽑을 사람의 수 K
	//M개의 장르를 평가
	//N명의 장르별 점수를 저장 (x번째 사람, x번째 사람의 점수)
	cin >> N >> M >> K; 
	for (int i = 0; i < M; i++) {  
		for (int j = 0; j < N; j++) { 
			cin >> people >> score;
			v.push_back(make_pair(people, score));
		}
	}

	sort(v.begin(), v.end(), compare); //정렬

	for (int i = 0; i < v.size(); i++) { //벡터를 순회한다.
		if (cnt == K) { //현재까지 뽑은 사람의 수가 선발해야 될 사람의 수와 같다면
			break; //종료
		}
		if (st.find(v[i].first) != st.end()) { //이미 뽑았던 사람이면
			continue; //반복문으로 돌아간다.
		}
		else { //이미 뽑은 사람이 아니면
			sum = sum + v[i].second; //그 사람의 점수를 더하고
			st.insert(v[i].first); //뽑은 사람으로 set에 넣는다.
			cnt++; //현재까지 뽑은 사람의 수를 증가시킨다.
		}
	}
	
	//cout으로 소숫점 첫번째 자리까지 찍기
	cout << fixed;
	cout.precision(1);
	cout << sum;
}