반응형

문제 출처 :


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



반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1212번] 8진수 2진수  (2) 2016.10.28
[2605번] 줄 세우기  (0) 2016.10.28
[2875번] 대회 or 인턴  (0) 2016.10.24
[2193번] 이친수  (0) 2016.10.14
[2910번] 빈도 정렬  (0) 2016.10.09