백준 2535번 [아시아 정보올림피아드](C++) -yes6686- 티스토리

백준 문제 풀이: 2535 [아시아 정보올림피아드]

---

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

문제 설명:

아시아 정보올림피아드에서 국가별 최대 2명의 수상자가 허용되며, 점수 순서대로 상위 3명을 선발하는 문제입니다. 각 참가자의 정보는 (국가 번호, 참가자 번호, 점수)로 주어집니다.

---

문제 해결 코드

// 아시아 정보올림피아드 문제의 최적화된 코드
#include <iostream>
#include <algorithm>
using namespace std;

// 참가자 정보를 저장하는 구조: (점수, (국가 번호, 참가자 번호))
pair<int, pair<int, int>> participants[101];
int countryCount[101]; // 국가별 수상자 수를 저장
int totalWinners = 3; // 총 수상자 수

// 점수를 기준으로 내림차순 정렬
bool compare(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
    return a.first > b.first;
}

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

    int n; // 참가자 수
    cin >> n;

    // 참가자 정보 입력
    for (int i = 0; i < n; i++) {
        cin >> participants[i].second.first // 국가 번호
            >> participants[i].second.second // 참가자 번호
            >> participants[i].first; // 점수
    }

    // 점수를 기준으로 정렬
    sort(participants, participants + n, compare);

    // 상위 3명의 수상자 선발
    for (int i = 0; i < n; i++) {
        if (totalWinners == 0) break; // 수상자 모집 완료
        int country = participants[i].second.first;
        if (countryCount[country] < 2) { // 국가별 최대 2명 제한
            countryCount[country]++;
            totalWinners--;
            cout << country << ' ' << participants[i].second.second << '\n';
        }
    }

    return 0;
}

---

코드 설명

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

• 핵심 알고리즘: 점수를 기준으로 내림차순 정렬한 후, 국가별 제한 조건을 고려하여 상위 3명의 수상자를 선발합니다.
• 구현 세부사항:
• sort: 점수를 기준으로 참가자를 정렬합니다.
• countryCount[country] < 2: 특정 국가에서 이미 2명이 수상했는지 확인합니다.
• totalWinners: 총 수상자 수가 3명에 도달하면 루프를 종료합니다.
• 시간 복잡도 분석:
• 정렬: O(n log n), 여기서 n은 참가자 수
• 수상자 선발: 최대 O(n)
• 전체 시간 복잡도: O(n log n)

---

결과

위 코드는 문제 조건을 만족하며, 점수와 국가별 제한 조건을 정확히 반영합니다. 정렬과 조건 기반 탐색을 통해 효율적으로 구현되었습니다.

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