[Codeground 2번] 프로그래밍 경진대회

문제 출처 :

https://www.codeground.org/practice/practiceProblemList

알고리즘 분석 :

문제 해결에 필요한 사항

1. 정렬

문제 이해를 위해 최고점이 어떻게 성립되는지 알아봐야 한다.

각 사람의 최종 라운드 이전까지의 점수가 주어지면 그 점수에 n을 더하면 최고점이 된다.

그렇다면 이를 해결하기위해 최종 라운드 이전까지에서 

마지막 라운드때 최고 득점 할 수 있는 최댓값을 구하기 위해 다음과 같은 작업을 한다.

정렬 후 n등부터 1등에게 각각 n-i점부터 1점까지 부여 -> 마지막 라운드에서 최고 득점 할 수 있는 최댓값

이 최댓값을 이용하여 문제를 해결한다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

#include <iostream> #include <cstdio> #include <algorithm>   #define max(a,b)(a > b ? a : b)   using namespace std;   int arr[300002];   int main() {     int tc;     scanf("%d", &tc);       for (int tCase = 1; tCase <= tc; tCase++)     {         int n;         int get = 0;           scanf("%d", &n);         for (int i = 0; i < n; i++)             scanf("%d", &arr[i]);           sort(arr, arr + n);           // 정렬 후 n등부터 1등에게 각각 n-i점부터 1점까지 부여한 후         // 마지막 라운드에서 최고 득점 할 수 있는 최댓값         for (int i = 0; i < n; i++)             get = max(get, arr[i] + n - i);           int cnt = 0;           // 현재 사람에 n점을 더할 때(최고점) get이상이면 cnt++         for (int i = 0; i < n; i++)             if (arr[i] + n >= get)                 cnt++;           printf("Case #%d\n%d\n", tCase, cnt);     }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus