백준 9017 - 크로스 컨트리

문제 설명

크로스 컨트리 달리기는 주자들이 자연적인 야외의 지형에 만들어진 코스를 달리는 운동 경기이다. 경주 코스는 일반적으로 4에서 12 킬로미터이며, 숲이나 넓은 땅을 통과하는 풀과 흙으로 된 지면과 언덕과 평평한 지형을 포함한다. 이 경기는 주자들의 개인성적을 매기고, 이를 가지고 팀의 점수를 계산한다. 

한 팀은 여섯 명의 선수로 구성되며, 팀 점수는 상위 네 명의 주자의 점수를 합하여 계산한다. 점수는 자격을 갖춘 팀의 주자들에게만 주어지며, 결승점을 통과한 순서대로 점수를 받는다. 이 점수를 더하여 가장 낮은 점수를 얻는 팀이 우승을 하게 된다. 여섯 명의 주자가 참가하지 못한 팀은 점수 계산에서 제외된다. 동점의 경우에는 다섯 번째 주자가 가장 빨리 들어온 팀이 우승하게 된다.

예를 들어, 다음의 표를 살펴보자.

팀 B 와 D 는 선수의 수가 여섯이 아니므로, 점수를 받을 수 없다. 팀 A 의 점수는 18 (1+4+6+7)이고, 팀 C 의 점수는 18 (2+3+5+8)이다. 이 경우 두 팀의 점수가 같으므로 다섯 번째로 결승점을 통과한 선수를 고려한다, A 팀의 다섯 번째 선수의 점수가 C 팀의 다섯 번째 선수의 점수보다 적으므로 A 팀이 우승팀이 된다.

모든 선수들의 등수가 주어질 때, 우승팀을 구하는 프로그램을 작성하라. 각 팀의 참가 선수가 여섯보다 작으면 그 팀은 점수 계산에서 제외됨을 주의하라. 여섯 명 보다 많은 선수가 참가하는 팀은 없고, 적어도 한 팀은 참가 선수가 여섯이며, 모든 선수는 끝까지 완주를 한다고 가정한다.

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 경기의 등수가 차례대로 주어지고 인원이 6명인 팀만 점수를 획득할 수 있다.

팀의 점수는 팀의 상위권 4명의 점수의 합이다.

팀 점수가 가장 낮은 팀이 우승한다.

만약, 팀 점수가 같은 팀이 있다면 5번째 선수가 먼저들어온 팀이 우승한다.

 

우선, 선수에게 개인 점수를 부여하고 이후 팀별로 모아 팀 점수를 계산하면 된다.

팀 점수를 계산하였다면 모든 팀의 점수를 확인하며 가장 적은 점수를 찾아 우승팀을 고르면 된다.

 

선수 개인 점수를 부여하는 부분은 간단하다.

입력시 팀 선수의 수를 세어본 뒤 6명이 안 되는 팀의 선수는 건너뛰며 점수를 매기면 된다.

vector<int> ranks(N);
map<int, vector<int>> teamCnt;
map<int, vector<int>> teamScore;
for (int i = 0; i < N; i++)
{
    cin >> ranks[i];
    teamCnt[ranks[i]].push_back(i);
}

int s = 1;
for (auto rank : ranks)
{
    if (teamCnt[rank].size() != 6) continue;
    teamScore[rank].push_back(s++);
}

 

이후, 각 팀을 살펴보며 상위 4명의 점수를 통해 팀 점수를 구하며 가장 작은 팀 점수를 고르면 된다.

int ans = 0;
int minScore = MAX;
for (auto [team, scores] : teamScore)
{
    int score = 0;
    for (int i = 0; i < 4; i++)
    {
        score += scores[i];
    }

    if (minScore == score)
    {
        if (teamScore[ans][4] > scores[4])
        {
            ans = team;
        }
    }
    else if (minScore > score)
    {
        ans = team;
        minScore = score;
    }
}

cout << ans << "\n";

---

 

 

 

 

 

전체 코드

#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, N;
const int MAX = 6'000;

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

    cin >> T;

    while (T--)
    {
        cin >> N;

        vector<int> ranks(N);
        map<int, vector<int>> teamCnt;
        map<int, vector<int>> teamScore;
        for (int i = 0; i < N; i++)
        {
            cin >> ranks[i];
            teamCnt[ranks[i]].push_back(i);
        }

        int s = 1;
        for (auto rank : ranks)
        {
            if (teamCnt[rank].size() != 6) continue;
            teamScore[rank].push_back(s++);
        }

        int ans = 0;
        int minScore = MAX;
        for (auto [team, scores] : teamScore)
        {
            int score = 0;
            for (int i = 0; i < 4; i++)
            {
                score += scores[i];
            }

            if (minScore == score)
            {
                if (teamScore[ans][4] > scores[4])
                {
                    ans = team;
                }
            }
            else if (minScore > score)
            {
                ans = team;
                minScore = score;
            }
        }

        cout << ans << "\n";
    }

    return 0;
}

---