[2790번] F7

문제 출처 :

https://www.acmicpc.net/problem/2790

알고리즘 분석 :

문제 해결에 필요한 사항

1. 문제의 함정 발견 능력

2. 내림차순 정렬

예시 입력 코드에 다음과 같이 되어있다.

3

8

10

9

이 코드를 내림차순 전렬하면 10 9 8이고 결국 10은 우승 할 수 있고, 9도 마지막 경기에서 이기면 12점으로 우승할 수 있고

8 또한 마지막 경기서 우승 시 11 11 11점으로 서로 공동우승 할 수 있다.

결국 이 문제를 보면 느끼게 되는 것이 예제 입력에 홀려 현재 가리키는 점수가 최고점을 받고 이전 최고점을 받은 점수가 최저점(1점)을 받으면 무조건 우승한다라고 판단하게 된다.

예를들어

8 10 9에서 8이 3점 10이 1점받으면 된다고 판단하게 될 수 있다.

하지만 1 3 3 3 을 보자.

3 3 3 1로 정렬 된 후, 1이 1등을 하여 5가 된다 보면 과연 우승 할 까?

4 5 6 5로 우승을 하지 못하게 된다.

그림을 통해 소스 코드를 확인 해 보자.

소스 코드 : 

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

#include <iostream> #include <algorithm>   using namespace std;   int a[300001];   bool cmp(const int &x,const int &y)  {     return x > y;  }   int main() {       int n; // 레이싱 선수 인원     int ans = 0; //우승 가능성이 있는 선수 인원     int need = 0; //필요한 점수          cin >> n;       for (int i = 0; i < n; i++)         cin >> a[i];       sort(a, a + n, cmp); // 내림차순 정렬       for (int i = 0; i < n; i++)      {         // 현재 해당하는 배열 값 + 최댓값이 필요점수 이상이 되면 +1          ans += (a[i] + n >= need);          // 필요점수의 최댓값을 구하는 식         need = max(need, a[i] + i + 1);      }     cout << ans;          return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus