백준 2790번 : F7

문제링크 :https://www.acmicpc.net/problem/2790

2790번: F7

 

 문제설명 

 

1. 레이싱을 하는데 마지막 레이싱을 남겨두고 현재 레이서들의 점수가 주어짐

2. 각 레이서들이 1등하면 N점 2등하면 N-1 점 ... 꼴등은 1점을 얻게됨

3. 우승할 확률이 조금이라도 있는 레이서의 수를 출력

 

 알고리즘 

 

1. 먼저 레이서의 점수를 내림차순으로 정렬

2. 맨 첫번째 인덱스 레이서는 우승을 무조건 할 수있으므로 초기값으로 잡아주고

3. 그다음 레이서 부터 레이서가 마지막경기를 1등한다고 가정 하여 점수를 N 더해준 값과 현재 꼴등+i등수의 점수에 1     점을 비교하여 1등한 레이서의 점수가 더 높으면 cnt++

 

 코드 

 

#include<iostream>
#include<algorithm>
using namespace std;
 
int arr[300001];
 
 
 
bool compare(int a, int b) {
    return a > b;
}
 
int main() {
    
    int N;
 
    int score = 0;
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
 
    //내림 차순 정렬
    sort(arr, arr + N, compare);
    
    score = arr[0] + 1;
    int result = 1;
 
    for (int i = 1; i < N; i++) {
        //1등할 가능성이 있다면 result++
        if (arr[i] + N >= score) result++;
 
        //비교할 점수를 계속 갱신
        score = max(score, arr[i] + i + 1);
    }
    cout << result;
}