algospot MATCHORDER

문제 링크입니다: https://algospot.com/judge/problem/read/MATCHORDER

N의 범위가 1~100이기 때문에 완전탐색법과 동적계획법을 사용하면 시간초과가 발생하는 문제였습니다.

따라서 탐욕 알고리즘을 사용하여 프로그램을 작성했습니다.

#include <iostream>

#include <algorithm>

#include <vector>

#include <set>

using namespace std;

 

int order(const vector<int> &russian, const vector<int> &korean)

{

        int length = russian.size(), wins = 0;

        //아직 남아 있는 선수들의 레이팅

        multiset<int> ratings(korean.begin(), korean.end()); //성적 순 정렬

       

        for (int rus = 0; rus < length; rus++)

        {

               //가장 레이팅 높은 한국 선수가 이길 수 없는 경우

               //가장 레이팅이 낮은 선수와 경기시킴

               if (*ratings.rbegin() < russian[rus])

                       ratings.erase(ratings.begin());

               //이 외의 경우 이길 수 있는 선수 중 가장 레이팅이 낮은 선수와 경기시킴

               else

               {

                       ratings.erase(ratings.lower_bound(russian[rus]));

                       wins++;

               }

        }

        return wins;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 1 || test_case>50)

               exit(-1);

 

        for (int i = 0; i < test_case; i++)

        {

               vector<int> russian; //러시아 선수들

               vector<int> korean; //한국 선수들

               int N;

               cin >> N;

               if (N < 1 || N>100)

                       exit(-1);

               //러시아 선수들 점수

               for (int j = 0; j < N; j++)

               {

                       int score;

                       cin >> score;

                       if (score < 1 || score>4000)

                              exit(-1);

                       russian.push_back(score);

               }

               //한국선수들 점수

               for (int j = 0; j < N; j++)

               {

                       int score;

                       cin >> score;

                       if (score < 1 || score>4000)

                              exit(-1);

                       korean.push_back(score);

               }

               cout << order(russian, korean) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략