백준 2865번 [나는 위대한 슈퍼스타K](C++) -yes6686- 티스토리

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

---

문제 링크: https://www.acmicpc.net/problem/2865

문제 설명:

참가자 n명과 심사위원 m명이 주어집니다. 각 심사위원은 참가자의 점수를 부여합니다. 각 참가자는 자신의 가장 높은 점수만을 유지합니다. k명의 참가자를 뽑아야 하며, 이때 뽑힌 참가자들의 점수 합이 최대가 되도록 하는 문제입니다.

---

문제 해결 코드

// 백준 2865 - 나는 위대한 슈퍼스타K
#include <iostream>
#include <algorithm>
using namespace std;

double arr[101]; // 각 참가자의 최고 점수를 저장할 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    cin >> n >> m >> k; // 참가자 수, 심사위원 수, 뽑을 참가자 수

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int a;
            double b;
            cin >> a >> b; // 참가자 번호와 점수 입력
            arr[a - 1] = max(arr[a - 1], b); // 최고 점수 갱신
        }
    }

    // 최고 점수를 내림차순으로 정렬
    sort(arr, arr + n, greater());

    double ans = 0; // 최고 점수 합
    for (int i = 0; i < k; i++) {
        ans += arr[i]; // 상위 k명 점수 합산
    }

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

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 각 참가자의 최고 점수를 저장한 뒤, 점수를 내림차순으로 정렬하여 상위 k명을 선택합니다.
• 구현 세부사항:
  • 심사위원 점수를 입력받을 때, 참가자의 최고 점수를 업데이트합니다.
  • 점수 배열을 내림차순으로 정렬하여 상위 k명을 뽑습니다.
  • fixed와 precision를 사용하여 소수점 첫째 자리까지 결과를 출력합니다.
• 시간 복잡도 분석:
  • 심사위원 점수 입력 및 최고 점수 갱신: O(n ⋅ m)
  • 점수 정렬: O(n log n)
  • 상위 k명 점수 합산: O(k)
  • 총 시간 복잡도: O(n ⋅ m + n log n)

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!