[백준] 2865: 나는 위대한 슈퍼스타K

SuKong·2020년 8월 28일

그리디 백준 알고리즘 정렬

BOJ의 알고리즘 문제를 풀어보아요

목록 보기

44/49

'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까지 이다.

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

예시 -
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

👉출력

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

예시 - 15.0

✍내 풀이

import java.util.*;

public class Main {		
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int peopNum = sc.nextInt();
		int genreNum = sc.nextInt();
		int finalNum = sc.nextInt();
		ArrayList <pair> list = new ArrayList();
		float answer = 0;
		ArrayList<Integer> finalidlist = new ArrayList();
		
		for( int i = 0 ; i < genreNum ; i++ ) {
			for( int j = 0 ; j < peopNum ; j++ ) {
				int id = sc.nextInt();
				float ability = sc.nextFloat();
				list.add(new pair(id, ability));
			}
		}
		Collections.sort(list, new Comparator<pair>() {
			@Override
			public int compare(pair o1, pair o2) {
				return Float.compare(o2.ability, o1.ability);
			}
		});
		for( pair thispair : list) {
			if(finalidlist.size() >= finalNum) break;
			if(!finalidlist.contains(thispair.id)) {
				answer += thispair.ability;
				finalidlist.add(thispair.id);
			}else {
				continue;
			}
		}
		System.out.printf("%.1f\n", answer);
	}
}
class pair{
	int id; 
	float ability;
	public pair(int id, float ability) {
		this.id = id;
		this.ability = ability;
	}
}