[BOJ/백준 2865][C++] 나는 위대한 슈퍼스타K

문제

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

백준 2865

백준 2865

 

문제 내용

참가자 n명의 m개 장르에 대한 능력치가 주어진다.

본선 진출 인원은 k명이고, 본선에서는 단 하나의 장르만 부를 수 있다.

상근이가 참가자별로 장르를 선택해주는데, 이때 본선 진출자들이 본선에서 고른 장르의 능력의 합을 구하면 된다.

 

문제 풀이

greedy문제이다.

일단 참가자별로 가장 높은 능력을 저장한다. (vector이용)

그리고 능력치를 내림차순으로 정렬한 뒤, 앞에서부터 k개를 더하여 출력하면 된다.

출력 시, 소수점 첫째 자리까지 반올림하여 출력하는 것에 유의하면 된다.

 

코드

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


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	//입력
	int n,m,k;
	cin >> n >> m >> k; //n명, m개 장르, 본선진출인원 k
	vector<float>arr(n, 0.0);
	
	int person; float ability;
	for (int i = 0; i < m; i++) { //장르
		for (int j = 0; j < n; j++) { //참가자별 능력
			cin >> person >> ability;

			//전체 장르를 통틀어, 참가자의 가장 높은 능력을 저장
			//사람 번호는 1번부터 시작하기 때문에 person-1
			arr[person - 1] = max(ability, arr[person - 1]);
		}
	}

	//문제 해결
	sort(arr.begin(), arr.end(),greater<float>()); //내림차순 정렬

	float ans = 0.0;
	for (int i = 0; i < k; i++) { 
		ans += arr[i]; //앞에서부터 k개 더하기
	}

	//결과 출력
	cout << fixed;
	cout.precision(1); //소수점 첫째짜리까지 출력
	cout << ans << '\n';
}