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

문제

권위를 자랑하는 레이싱 대회 F7이 열릴 예정이다. F7은 드라이버의 순위가 자주 바뀌기 때문에 사람들에게 인기가 아주 많다. 상근이는 F7 레이싱의 엄청난 팬이지만, 마지막 레이싱과 중간고사가 겹쳐서 갈 수 없게 되었다.

지금은 마지막 레이싱을 제외한 나머지 레이싱이 모두 종료된 상황이다. 상근이는 우승을 할 수 있는 사람의 수를 알아보려고 한다. F7의 우승자는 각 레이싱을 통해서 얻은 점수의 합이며, 점수가 가장 높은 사람이 우승을 하게 된다.

마지막 레이싱에서 1등을 한 사람은 N점을 얻게 되고, 2등은 N-1점, ..., 꼴등은 1점을 얻게 된다. 각 레이싱에서 두 드라이버의 등수가 같은 경우는 없다.

마지막 레이싱을 하기 바로 전에 각 드라이버의 점수가 주어졌을 때, 우승을 할 가능성이 있는 사람의 수를 구하는 프로그램을 작성하시오. 만약 점수의 합이 가장 큰 사람이 여러 명이라면, 여러명 다 우승자이다.

입력

첫째 줄에 F7에 참가하는 드라이버의 수 N (3 ≤ N ≤ 300,000)이 주어진다.

다음 N개 줄에는 각 드라이버가 마지막 레이싱을 하기 전까지 얻은 점수 Bi가 주어진다. (0 ≤ Bi ≤ 2,000,000, i = 1, ..., N)

출력

첫째 줄에 F7을 우승할 가능성이 있는 사람의 수를 출력한다.

예제 입출력

• 예제 입력 1

3
8
10
9

• 예제 출력 1

3

• 예제 입력 2

5
15
14
15
12
14

• 예제 출력 2

4

Solution

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N; cin >> N;
    int answer = 1;
    vector<int> racer(N);
    for(int i = 0; i < N; i++){
        cin >> racer[i];
    }
    sort(racer.begin(), racer.end(), greater<int>());
    int score = racer[0] + 1;
    for(int i = 1; i < N; i++){
        if(racer[i] + N >= score){
            answer++;
        }
        score = max(score, racer[i] + i  + 1);
    }
    cout << answer << '\n';   
}

Greedy 문제의 가장 빡센 점은, 단순히 알고리즘 빨로 해결할 수 없는 것이라 생각한다.
문제를 이해하고 기똥찬 방법을 생각 해 내야 하는 것...참 쉽지 않다.

앞으로 남은 한 해는 알고리즘도 알고리즘이지만, 그리디와 시뮬레이션 위주로 계속 풀어보며 시간을 보낼까 한다.

일단 문제는 간단하다. 어떤 놈이 우승할 가능성이 있느냐.

3
8
10
9

이 상황에서 상식적으로 우승을 할 가능성이 높은 사람은 10점을 가지고 있는 사람이다.
10점을 가지고 있는 사람 외에 우승을 할 가능성이 있을 법한 사람은 10점보다 높은 점수를 가진 사람이어야 한다.
마찬가지 이유로 이 문제에서 정답은 1보다 작을 수 없다.

sort(racer.begin(), racer.end(), greater<int>());
int score = racer[0] + 1;
for(int i = 1; i < N; i++){
    if(racer[i] + N >= score){
        answer++;
    }
    score = max(score, racer[i] + i  + 1);
}
cout << answer << '\n';  

자 그럼 나머지 데이터를 보자. 마지막 레이싱에서 1등을 먹으면 N점을 받을 수 있다. 즉 이 점수가 현재 우승의 최소 조건보다 크다면 그 선수는 우승을 할 가능성이 었는 선수다.
그 다음 for문을 돌릴때마다 우승을 할 수 있는 가능성이 있다를 판별할 값은 이전 점수와 현재 선수의 점수 + 현재 선수의 정렬 순서 + 1과 비교해서 큰값으로 처리한다.
이렇게 하는 이유는 우선 이미 내림차순으로 정렬을 했다. 우승을 하려면 이 사람만 넘어야 하는 게 아니다.

어려운 문제는 아니지만, 특별히 알고리즘을 써서 푸는 문제가 아니라 수리적 사고력을 활용해야 한다.

개인적인 생각이지만 Solved.ac 티어는 금방 찍는다. 문제는 진짜 이런 문제들을 어떻게 접근하느냐라고 생각한다. 최근 들어 PS에 소홀했단 생각이 들어서 어떻게든 주중에는 문제를 풀고 리뷰해 보려고 노력 해 보겠다....