1R/2016 07 05

오늘의 문제

경진대회

참가자

이름	학번
박인서	15학번

코드

박인서

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	setbuf(stdout, NULL);
	
	int TC;
	int test_case;
    
	scanf("%d", &TC);
	for(test_case = 1; test_case <= TC; test_case++) {
	    int n;
	    vector<int> a;
	    scanf("%d", &n);
	    for(int i=0;i<n;i++){
	        int t;
	        scanf("%d", &t);
	        a.push_back(t);
	    }
	    sort(a.begin(),a.end());
	    
	    //마지막 대회 시행 및 1등 점수 저장
	    int max=0;
	    for(int i=0;i<n;i++)
	        if(max<a[i]+n-i) max=a[i]+n-i;
	    
	    //1등 가능성 따짐
	    int cnt=0;
	    for(int i=0;i<n;i++)
	        if(max<=a[i]+n) cnt++;

	    printf("Case #%d\n%d\n", test_case, cnt);
	}
	return 0;
}

아이디어

박인서

• 마지막 대회에서 종합 점수 1등이 1점, 2등이 2점, ... , n등이 n점일 때 1등 가능성이 가장 많아짐.
• 따라서 마지막 대회가 위와 같이 이상적으로 이루어진다고 가정하고, 마지막 대회 결과 최댓값을 각자가 1등 하였을 때를 비교한다.