[C++] 코드그라운드 연습문제 프로그래밍 경진대회 문제풀이

문제링크

코드그라운드 연습문제 프로그래밍 경진대회

codeground

간단하지만 효율적인 알고리즘이 잘 떠오르지 않는 문제이다. 문제에서 각 라운드 마다 받은 점수의 합이 제일 높은 사람이 우승한다고 하였는데 이는 우승자가 여러명일 수도 있다는 이야기이다. 이 조건이 이해가 되지 않아 질문이 많은 문제이다.

구하려는 것은 우승이 가능한 사람의 수이므로 각 점수에다 최대치(N)를 더한 점수가 어떤 기준점수를 넘는지 안넘는지 판단하면 된다. 여기서 기준점수는 다른 모든 점수들을 최저로 만든뒤 그 점수들 중 최고인 점수이다. 

따라서 이전 라운드까지의 점수에서 최대치(N)를 더한 점수가 최저가 될 수 있는 점수의 후보들의 최대값과 비교해 크거나 같다면 우승할 가능성이 있는 후보인 것이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int Answer,n;
 
 
int main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T, test_case;
 
 
    cin >> T;
    for(test_case = 0; test_case  < T; test_case++)
    {
        int max=0;
        Answer = 0;
 
        cin>>n;
        vector <int> scores(n,0);
        for(int i=0;i<n;i++) cin>>scores[i];
       
 
        //정렬하고
        sort(scores.begin(),scores.end());
        
 
        //최저후보점수의 최대값을 구한뒤
        for(int i=0;i<n;i++){
            int tmep=scores[i]+n-i;
            if(max<tmep)max=tmep;
        }
    
        //각 점수와 비교해 최대값이상이면 우승할 가능성이 있는 후보이므로 정답을 증가 
        for(int i=0;i<n;i++){
            if(scores[i]+n>=max)Answer++;
        }
 
 
        cout << "Case #" << test_case+1 << endl;
        cout << Answer << endl;
    }
 
    return 0;
}