[Baekjoon/C++] 3758번 - KCPC

[백준] Baekjoon Online Judge

문제로 이동

 

문제

당신은 유명 프로그래밍 대회인 KCPC(Korean Collegiate Programming Contest)에 참가하고 있다. 이 대회에서 총 k개의 문제를 풀게 되는데, 어떤 문제에 대한 풀이를 서버에 제출하면 그 문제에 대해 0점에서 100점 사이의 점수를 얻는다. 풀이를 제출한 팀의 ID, 문제 번호, 점수가 서버의 로그에 제출되는 시간 순서대로 저장된다. 한 문제에 대한 풀이를 여러 번 제출할 수 있는데, 그 중 최고 점수가 그 문제에 대한 최종 점수가 된다. (만약 어떤 문제에 대해 풀이를 한번도 제출하지 않았으면 그 문제에 대한 최종 점수는 0점이다.) 

당신 팀의 최종 점수는 각 문제에 대해 받은 점수의 총합이고, 당신의 순위는 (당신 팀보다 높은 점수를 받은 팀의 수)+1 이다. 

점수가 동일한 팀이 여럿 있을 수 있는데, 그 경우에는 다음 규칙에 의해서 순위가 정해진다. 

1. 최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다. 
2. 최종 점수도 같고 제출 횟수도 같은 경우, 마지막 제출 시간이 더 빠른 팀의 순위가 높다. 

동시에 제출되는 풀이는 없고, 모든 팀이 적어도 한 번은 풀이를 제출한다고 가정하라. 

서버의 로그가 주어졌을 때, 당신 팀의 순위를 계산하는 프로그램을 작성하시오.

 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 팀의 개수 n, 문제의 개수 k, 당신 팀의 ID t, 로그 엔트리의 개수 m을 나타내는 4 개의 정수가 주어진다. 여기서, 3 ≤ n, k ≤ 100, 1 ≤ t ≤ n, 3 ≤ m ≤ 10,000이다. 그 다음 m개의 줄에는 각 풀이에 대한 정보가 제출되는 순서대로 주어진다. 각 줄에는 팀 ID i, 문제 번호 j, 획득한 점수 s를 나타내는 세 개의 정수가 주어진다. 여기서 1 ≤ i ≤ n, 1 ≤ j ≤ k, 0 ≤ s ≤ 100이다. 

 

출력

출력은 표준출력을 사용한다. 주어진 각 테스트 데이터에 대해 당신 팀의 순위를 한 줄에 출력하여야 한다

 

---

풀이

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 101

struct Team {
    int id = 0;     // 팀 ID
    int score = 0;  // 획득한 점수
    int cnt = 0;    // 제출 횟수
    int last = 0;   // 마지막 제출 시간
};

Team team[MAX];
int score[MAX][MAX];

void init();
bool compare(Team a, Team b);

// 배열 초기화
void init() {
    for (int i = 0; i < MAX; i++) {
        team[i] = { i, 0, 0, 0 };

        for (int j = 0; j < MAX; j++) score[i][j] = 0;
    }
}

bool compare(Team a, Team b) {
    if (a.score == b.score) {
        if (a.cnt == b.cnt) return a.last < b.last;

        return a.cnt < b.cnt;
    }

    return a.score > b.score;
}

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

    int T;
    cin >> T;

    while (T--) {
        int n, k, t, m;
        cin >> n >> k >> t >> m;

        init();

        for (int i = 0; i < m; i++) {
            int id, j, s;
            cin >> id >> j >> s;

            team[id].cnt++;
            team[id].last = i;
            score[id][j] = max(score[id][j], s);
        }

        // 각 팀의 점수 계산
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) 
                team[i].score += score[i][j];
        }

        sort(team + 1, team + n + 1, compare);

        // 우리 팀의 등수 찾기
        for (int i = 1; i <= n; i++) {
            if (team[i].id == t) {
                cout << i << '\n';
                break;
            }
        }
    }

    return 0;
}

 

struct Team {
    int id = 0;     // 팀 ID
    int score = 0;  // 획득한 점수
    int cnt = 0;    // 제출 횟수
    int last = 0;   // 마지막 제출 시간
};

 팀의 순위를 매기기 위해 필요한 정보를 묶어 놓은 구조체이다.

 

// 배열 초기화
void init() {
    for (int i = 0; i < MAX; i++) {
        team[i] = { i, 0, 0, 0 };

        for (int j = 0; j < MAX; j++) score[i][j] = 0;
    }
}

 다음 테스트 데이터를 위해 배열을 초기화하는 함수이다.

 

bool compare(Team a, Team b) {
    if (a.score == b.score) {
        if (a.cnt == b.cnt) return a.last < b.last;

        return a.cnt < b.cnt;
    }

    return a.score > b.score;
}

 문제에서 주어진 정렬 방법을 구현한 함수이다.

 

        for (int i = 0; i < m; i++) {
            int id, j, s;
            cin >> id >> j >> s;

            team[id].cnt++;
            team[id].last = i;
            score[id][j] = max(score[id][j], s);
        }

 데이터를 입력 받는 부분의 코드이다. 풀이를 제출한 횟수를 증가시키고, 마지막 제출 시간을 team에 기록한다. 또한 제출한 풀이의 점수와 기존의 점수 중 더 큰 것을 score에 저장한다. 한 문제에 대한 풀이를 여러 번 제출할 수 있고, 그 중 최고 점수가 그 문제의 최종 점수가 되기 때문이다.

 

        // 각 팀의 점수 계산
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) 
                team[i].score += score[i][j];
        }

 위에서 기록한 각 점수별 기록을 모두 합쳐서 각 팀의 점수를 계산하는 부분의 코드이다.

 

        sort(team + 1, team + n + 1, compare);

        // 우리 팀의 등수 찾기
        for (int i = 1; i <= n; i++) {
            if (team[i].id == t) {
                cout << i << '\n';
                break;
            }
        }

 그 후 team을 정렬하고, for문으로 배열을 탐색하여 팀의 등수를 찾는다. 이때 팀은 1번부터 시작하므로 정렬과 반복문의 시작점이 1이 되어야 한다.