[BOJ] 21319 - 챔피언(Easy)

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

BOJ - 챔피언(Easy)

문제 유형: 그리디, 이분 탐색, 시뮬레이션

문제 난이도: Gold I

시간 제한: 2초

메모리 제한: 1024MB

 

문제

입력 조건 외 챔피언 (Hard)와의 차이는 없다.

민겸이는 세계적인 격투기 선수 육성 회사의 회장이다. 민겸이는 격투기 선수의 영입을 위해 세계 격투기 챔피언십을 관람하기로 했다. 세계 격투기 챔피언십의 규칙은 아래와 같다.

격투기 선수는 N명이고, 일렬로 서 있다. 선수들은 각각 전투력을 가지고 있다. 격투기 선수들은 양쪽으로 이웃한 두 명의 선수들 중 한 명에게 싸움을 걸어 격투를 벌인다. 이 때, 전투력이 높은 격투기 선수가 승리한다. 격투에서 승리한 선수는 자신감이 붙어 전투력이 1 증가한다. 패배한 선수는 경기장을 빠져나가며 패배한 선수의 양 옆으로 이웃한 선수가 서로 이웃하게 된다. 전투력이 같은 두 선수가 격투를 벌이면 결판이 나지 않기 때문에 격투가 취소된다. 또한, 두 명의 선수가 격투를 하고 있을 때, 다른 선수들은 모두 그 시합을 지켜보느라 바쁘기 때문에 격투를 하지 않는다. 격투를 0회 이상 진행하여 마지막에 유일한 선수가 남는다면, 그 선수는 챔피언이 된다.

민겸이는 돈이 아주 많기 때문에, 세계 격투기 챔피언십에서 챔피언이 될 가능성이 있는 선수들을 모두 영입하려고 한다. 격투기 선수들의 전투력이 주어졌을 때, 민겸이가 영입해야 할 격투기 선수들을 민겸이에게 알려주자!

 

입력

입력은 두 줄로 주어진다.

첫 번째 줄에는 격투기 선수의 수 N(1 ≤ N ≤ 200,000)이 주어진다.

두 번째 줄에는 1번부터 N번까지 각 격투기 선수의 전투력 a1, a2, …, aN(1 ≤ ai ≤ 109, 1 ≤ i ≤ N) 이 정수로 순서대로 주어진다.

단, 각 격투기 선수들의 초기 전투력은 비내림차순으로 정렬되어 있다.

 

출력

챔피언이 될 수 있는 격투기 선수들의 번호를 공백으로 구분하여 오름차순으로 출력한다. 각 선수들의 번호는 1부터 N까지이다.

만약 아무도 챔피언이 될 수 없다면, -1을 출력한다.

 

풀이

각 선수들이 이진탐색으로 최대 어디까지 이길 수 있는지 계산할 것이다.

우선, 처음에 싸워서 이기려면, 자신이 같은 수들 중에서 가장 왼쪽에 있어야 한다. 그래야 자신보다 작은 상대를 잡아서 성장할 수 있기 때문이다.

lower_bound를 시도해서 그 인덱스가 자신이 아니라면, 애초에 불가능하다.

이제, 자신 이전의 모두를 이길 수 있다는 전제를 하고, 자신보다 왼쪽에 있는 요소들의 개수를 현재 크기에 누적한다.

이제 이진탐색으로 이 크기로 어디까지 먹을 수 있는지 계산한다.

만약 먹을 수 있는게 없다면 false를 반환하고, 계속 반복해서 모두를 이겼다면 true를 반환한다.

만약 우승할 수 있다면 배열에 담는다.

 

정답배열이 비어있으면 -1을 출력하고, 아니라면 1-indexed로 변환해서 출력해주자.

 

코드

C++

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

int n;

bool check(int i, vector<int> &a) {
    ll grown = a[i];
    int lb = lower_bound(a.begin(), a.end(), grown) - a.begin();

    if (lb < i) {
        return false;
    }
    grown += lb;

    int nextIdx = i + 1;
    while (nextIdx < n) {
        int gain = lower_bound(a.begin() + nextIdx, a.end(), grown) -
                   (a.begin() + nextIdx);
        if (gain == 0) return false;
        grown += gain;
        nextIdx += gain;
    }
    return true;
}

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    vector<int> a(n);
    for (auto &i : a) {
        cin >> i;
    }

    vector<int> ans;
    for (int i = 0; i < n; i++) {
        if (check(i, a)) ans.emplace_back(i + 1);
    }

    if (ans.empty())
        cout << "-1\n";
    else {
        for (const auto &answer : ans) {
            cout << answer << " ";
        }
        cout << "\n";
    }
    return 0;
}