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

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

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	1279	509	439	41.572%

---

문제

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

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

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

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

---

입력

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

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

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

---

출력

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

---

예제 입력 1

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

예제 출력 1

15.0

---

출처

• Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #3 3번
  • 문제를 번역한 사람: baekjoon

---

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 정렬
• 우선순위 큐

---

소스코드

import sys

input = sys.stdin.readline

N, M, K = map(int, input().split())

skills = {}

for i in range(N):
    skills[i + 1] = 0

for i in range(M):
    genre = list(map(float, input().split()))

    for j in range(0, N * 2, 2):
        if genre[j + 1] > skills[genre[j]]:
            skills[genre[j]] = genre[j + 1]
    # print(skills)
score = sorted(list(skills.values()), reverse=True)
# print(score)
total_sum = sum(score[:K])
print('%.1f' % total_sum)