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

문제링크

문제

상근이는 한국 최고의 가수를 뽑는 "나는 위대한 슈퍼스타K"의 감독이다. 상근이는 다음과 같이 참가자를 선발하려고 한다.

"나는 위대한 슈퍼스타K"의 예선에는 N명이 참가했고, 서로 다른 M개 장르에 대한 오디션을 보았다. 심사위원은 모든 참가자의 각 장르에 대한 능력을 점수로 매겼다. 이 점수는 실수로 나타낸다.

본선에는 총 K명이 나갈 수 있다. 각 참가자는 본선에서 단 하나의 장르만 부를 수 있고, 이 장르는 상근이가 정해준다. 한 사람이 여러 장르를 부를 수는 없지만, 여러 사람이 같은 장르를 부를 수는 있다.

모든 참가자의 각 장르에 대한 능력이 주어진다. 이때, 능력의 합이 최대가 되도록 참가자와 장르를 선택하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, K가 주어진다. (1 ≤ M ≤ 100, 1 ≤ K ≤ N ≤ 100)

다음 M개의 줄은 각 장르에 대한 참가자의 능력이 주어진다. 이 줄에는 N개의 (i, s)쌍이 주어진다. 여기서 i는 참가자의 번호, s는 그 참가자의 장르에 대한 능력이다. 이 쌍은 능력이 감소하는 순서대로 주어진다. 참가자의 번호는 1부터 N까지 이다.

각 줄에 모든 학생은 한 번씩 등장한다.

출력

첫째 줄에 본선 참가자의 능력의 합을 소수점 첫째자리까지 반올림해 출력한다.

예제 입력 / 출력

// 예제 입력 1
3 2 2
2 3.0 1 0.2 3 0.1
3 1.0 2 0.5 1 0.2

// 예제 출력 1
4.0

// 예제 입력 2
4 4 3
4 5.0 2 4.0 3 2.0 1 1.0
2 2.0 3 1.0 1 0.5 4 0.3
4 6.0 3 5.0 2 2.0 1 0.0
1 4.0 2 3.0 4 0.6 3 0.3

// 예제 출력 2
15.0

풀이

📍 알고리즘

• 이 문제는 능력의 합이 최대가 되는 값을 구하는 문제이므로 최적의 해를 찾는 그리디 알고리즘을 사용해야 한다.

• 참가자들의 각 장르별로 주어진 능력치 중 최대의 값들을 내림차순으로 정렬하여 앞에서 부터 본선 참가자 수인 K개를 골라 더하면 능력의 합이 최대가 되는 값을 구할 수 있다.

EX. 예제2

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

float ability[101][101];

bool standard(float a, float b) {
	return a > b;
}

int main(void) {

	int N, M, K, person;
	float max, sum = 0;
	vector<float> abilities;

	cin >> N >> M >> K;

	for (int i = 1; i <= M; i++) {
		for (int j = 0; j < N; j++) {
			cin >> person;
			cin >> ability[person][i];
		}
	}

	for (int i = 1; i <= N; i++) {
		max = *max_element(ability[i] + 1, ability[i] + M + 1);
		abilities.push_back(max);
	}

	sort(abilities.begin(), abilities.end(), standard);

	for (int i = 0; i < K; i++) {
		sum += abilities[i];
	}

	cout << fixed;
	cout.precision(1);
	cout << sum;
}