[C++] 백준 21319번: 챔피언 (Easy) - Greedy

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

21319번: 챔피언 (Easy)

 

저번주에 2022 IGRUS Newbie Programming Contest Open에 참여한 후에

오늘 여행 가기전에 잠깐 시간이 남아 2020년도에 열렸던 같은 대회의 문제도 풀어보려고 들어가봤다

 

N의 범위가 1 <= N <= 200,000 이므로

하나하나 다 확인하며 넘어가는 것은 당연히 TLE가 날것이라고 생각했다.

 

그래서 생각한 방법은

처음 입력이 비내림차순으로 정렬되어있는 것을 보면서

임의의 위치 i에 대하여 i보다 작은 수가 왼쪽 (i - 1위치)에 존재하면  그 i의 왼쪽에 있는 사람들은 모두 이길 수 있다는 소리이다.

또한, i가 왼쪽 모두를 이겼다면 i번째 사람의 전투력은 현재 전투력 + (i - 1)이 될 것이고,

오른쪽에 있는 사람들의 전투력만 비교하면 된다.

 

그렇기에 오른쪽 사람들의 전투력만 비교해주면 되는데,

역시 현재 i의 위치에서 오른쪽에 있는 전투력 중 가장 높으면서 i의 위치와 차이나는 거리만큼을 빼주면 된다.

 

무슨 말이냐면,

현재 i에 위치한 사람의 전투력을 j라고 하고, i + 3에 위치한 사람의 전투력을 k라고 한다면,

i는 i + 1, i + 2를 이겨가며 j + 2의 전투력을 가질 것이다.

만약 j + 2 > k 이기만 한다면 i에 위치한 사람은 챔피언이 될 수 있을 것이다.

그렇기에 i의 오른쪽에 위치한 사람 중 가장 전투력에서 i와의 거리 차이를 뺀 값이 가장 큰 사람만을 이긴다면 i는 챔피언이 될 수 있다.

 

#include <iostream>
using namespace std;
int dp[200001];
int arr[200001];
bool c;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    for(int i=1; i<=n; i++){
        cin >> dp[i];
    }
    if(n==1){
        cout << 1;
        return 0;
    }
    arr[n]=dp[n];
    for(int i=n-1; i>=1; i--){
       arr[i]=max(arr[i+1]-1, dp[i+1]);
    }
    for(int i=1; i<=n; i++){
        int t;
        if(dp[i]>dp[i-1]) {
            t=dp[i]+i-1;
            if(t>arr[i]) c=true, cout << i << " ";
        }
    }
    if(!c){
        cout << -1;
        return 0;
    }
}