백준 3758 - KCPC

문제 설명

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

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

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, n개의 팀이 k개의 문제를 푸는 대회에서 각 팀이 얻은 점수를 통해 순위를 매긴다.

이때, t라는 팀의 순위를 구하면 된다.

순위를 구하는 기준은 다음과 같다.

1. 총점수가 높은 팀이 순위가 높다.
2. 총점수가 같다면 제출 횟수가 적은 팀이 순위가 높다.
3. 총점수와 제출 횟수가 같다면 마지막 제출이 빠른 팀이 순위가 높다.

 

해당 문제는 팀 순위와 관련된 정보를 구조체로 만들고 이를 정렬하면 쉽게 해결할 수 있다.

팀 순위와 관련된 정보는 총 3가지 이다.

• 총점수
• 제출 횟수
• 마지막 제출 시간

이를 구조체로 만들면 다음과 같다.

struct TeamScore
{
    TeamScore(int id):
        teamID(id)
    {
        scores.assign(k, 0);
    }

    int teamID;
    vector<int> scores;
    int totalScore = 0;
    int lastSubmitTime = 0;
    int submitCount = 0;

    void UpdateScore(int testNum, int score, int time)
    {
        submitCount++;
        lastSubmitTime = time;
        if (scores[testNum] < score)
        {
            totalScore += score - scores[testNum];
            scores[testNum] = score;
        }
    }

    bool operator <(const TeamScore& Other)
    {
        if (totalScore != Other.totalScore) return totalScore > Other.totalScore;
        if (submitCount != Other.submitCount) return submitCount < Other.submitCount;
        return lastSubmitTime < Other.lastSubmitTime;
    }
};

마지막에 t라는 팀의 순위를 구해야 하기 때문에 id를 설정하여 식별하였다.

UpdateScore는 해당 팀의 점수를 갱신해 주는 함수이다.

문제 번호와 점수, 제출 시간이 매개변수로 들어오면 해당 문제의 점수와 비교하여 점수를 갱신한다.

즉, UpdateScore는 하나의 제출과 동일한 것이다.

따라서, 해당 함수에서 제출 횟수와 마지막 제출 시간을 갱신해 준다.

 

점수 및 정보를 갱신하는 작업이 끝나면 정렬을 통해 순위를 매기면 된다.

연산자 오버로딩을 통해 정렬 기준을 설정해 준다.

가장 우선시되는 기준은 총점수이다.

이후, 제출 횟수, 마지막 제출 시간을 기준으로 정렬해 준다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int T;
int n, k, t, m;

struct TeamScore
{
    TeamScore(int id):
        teamID(id)
    {
        scores.assign(k, 0);
    }

    int teamID;
    vector<int> scores;
    int totalScore = 0;
    int lastSubmitTime = 0;
    int submitCount = 0;

    void UpdateScore(int testNum, int score, int time)
    {
        submitCount++;
        lastSubmitTime = time;
        if (scores[testNum] < score)
        {
            totalScore += score - scores[testNum];
            scores[testNum] = score;
        }
    }

    bool operator <(const TeamScore& Other)
    {
        if (totalScore != Other.totalScore) return totalScore > Other.totalScore;
        if (submitCount != Other.submitCount) return submitCount < Other.submitCount;
        return lastSubmitTime < Other.lastSubmitTime;
    }
};


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> T;

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

        vector<TeamScore> Teams;
        for (int i = 0; i < n; i++)
        {
            Teams.push_back(TeamScore(i));
        }

        for (int i = 0; i < m; i++)
        {
            int team, test, score;
            cin >> team >> test >> score;

            Teams[team-1].UpdateScore(test-1, score, i);
        }

        sort(Teams.begin(), Teams.end());

        for (int i = 0 ; i < n; i++)
        {
            if (Teams[i].teamID == t-1)
            {
                cout << i + 1 << "\n";
                break;
            }
        }
    }

    return 0;
}

---