[Baekjoon - 25449] Eurokulen

난이도: Silver V

 

태그

• Sort

 

풀이

0. 시작하기 전: 간단한 정의

\( A_{i, x} \)은 \( i \)번째 참가자가 \( x \)점을 준 참가자의 번호를 의미합니다.

이 값은 \( i \)번째 참가자가 \( N-x \)위를 준 참가자의 번호와 일치합니다.

 

1. 각 참가자의 점수는 어떻게 정할까?

\( i \)번 참가자의 점수를 계산해봅시다.

이는, \( A_{j, x} = i \)를 만족하는 모든 \( (j, x) \) 순서쌍에 대해, \( x \)점씩 추가로 더해주면 됩니다.

 

참가자의 점수를 1명씩 계산해야 할 필요는 없으니, \( A_{i, x} \)를 돌아보면서 \( A_{i, x} \)번 참가자에 \( x \)점을 더해주면 됩니다.

 

이 뒤로 남은 건 점수 순 내림차순 정렬하고 1, 2, 3위를 출력하는 거죠.

 

2. '점수 교환'은 어떻게 판별할까?

두 참가자 \( i, j \) 간의 점수 교환이 발생하려면, 어떤 \( x \)에 대해 \( A_{i, x} = j \)이고 \( A_{j, x} = i \)여야 합니다.

이를 나이브하고 \( i, j, x \)에 대해 돌리면 \( O(N^3) \)의 시간이 됩니다.

 

그런데, \( A_{i, x} = j \)라는 조건을 잘 생각해보면 \( i, x \)만 돌리고 \( j \)는 \( A_{i, x} \)에서 들고 온 다음에 판별할 수 있기 때문에, \( i, x \)에 대해서만 반복문을 돌리면 \( O(N^2) \)으로 계산할 수 있습니다.

 

두 참가자 \( i, j \) 간의 점수 교환이 발생되었다면, \( i \)번 참가자와 \( j \)번 참가자에 표시를 해두고

최종 점수는 표시가 안 된 참가자들의 투표에 대해서만 계산해주면 됩니다.

 

3. 코드

int arr[1020][1020];
pi2 res[1020];
bool chk[1020];
 
void Main(){
    int n; cin >> n;
    for (int i = 1; i <= n; i++){
        for (int j = n-1; j >= 1; j--){ cin >> arr[i][j]; }
    }
    for (int i = 1; i <= n; i++){ res[i] = {0, i}; }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n-1; j++){ res[ arr[i][j] ].fr += j; }
    }
    sort(res+1, res+n+1, [](pi2 a, pi2 b){
        if (a.fr != b.fr){ return a.fr > b.fr; }
        return a.sc < b.sc;
    });
    cout << res[1].sc << ' ' << res[2].sc << ' ' << res[3].sc << endl;
    for (int i = 1; i <= n; i++){
        for (int x = 1; x <= n-1; x++){
            int j = arr[i][x];
            if (arr[j][x] == i){ chk[i] = chk[j] = 1; }
        }
    }
    for (int i = 1; i <= n; i++){ res[i] = {0, i}; }
    for (int i = 1; i <= n; i++){
        if (chk[i]){ continue; }
        for (int j = 1; j <= n-1; j++){ res[ arr[i][j] ].fr += j; }
    }
    sort(res+1, res+n+1, [](pi2 a, pi2 b){
        if (a.fr != b.fr){ return a.fr > b.fr; }
        return a.sc < b.sc;
    });
    cout << res[1].sc << ' ' << res[2].sc << ' ' << res[3].sc << endl;
}