1R/2016 07 05

오늘의 문제

경진대회

참가자

이름	학번
박인서	15학번
15이원준	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;
}

이원준

// 아래 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, char** argv) {
	/* 아래 freopen 함수는 input.txt 를 read only 형식으로 연 후,
	앞으로 표준 입력(키보드) 대신 input.txt 파일로 부터 읽어오겠다는 의미의 코드입니다.
	만약 본인의 PC 에서 테스트 할 때는, 입력값을 input.txt에 저장한 후 freopen 함수를 사용하면,
	그 아래에서 scanf 함수 또는 cin을 사용하여 표준입력 대신 input.txt 파일로 부터 입력값을 읽어 올 수 있습니다.
	또한, 본인 PC에서 freopen 함수를 사용하지 않고 표준입력을 사용하여 테스트하셔도 무방합니다.
	단, Codeground 시스템에서 "제출하기" 할 때에는 반드시 freopen 함수를 지우거나 주석(//) 처리 하셔야 합니다. */
	//freopen("input.txt", "r", stdin);

	setbuf(stdout, NULL);

	int TC;
	int test_case;

	scanf("%d", &TC);	// cin 사용 가능
	for (test_case = 1; test_case <= TC; test_case++) {
		// 이 부분에서 알고리즘 프로그램을 작성하십시오.
		int n;
		int temp;
		vector<int> vec;
		scanf("%d", &n);
		int ans;
		for (int i = 0; i < n; i++){
			scanf("%d", &temp);
			vec.push_back(temp);
		}
		sort(vec.begin(), vec.end());
		int max = 0;
		for (int i = 0; i < n; i++){
			if (vec[i] + n - i > max) max = vec[i] + n - i;
		}
		for (int i = 0; i < n; i++){
			if (vec[i] + n >= max){
				ans = n - i;
				break;
			}
		}

		// 이 부분에서 정답을 출력하십시오.
		printf("Case #%d\n", test_case);	// cout 사용 가능
		printf("%d\n", ans);
	}

	return 0;	// 정상종료 시 반드시 0을 리턴해야 합니다.
}

아이디어

박인서

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

15이원준

• 위와 같습니다.
• 다만 저는 작은 점수부터 체크하며 i번째가 가능하다면 i+1부터는 당연히 가능하다는 것을 이용하여 답을 구했습니다.