[백준 2262] 토너먼트 만들기 C++

2262번: 토너먼트 만들기

그리디

---

랭킹이 높은 사람이 반드시 이기기 때문에 우승자는 항상 1번이다.

 

부전승이 여러번 있어도 상관없기 때문에 매번 가장 랭킹이 낮은 사람(번호가 높은 사람)만 경기를 하게 했다.

 

랭킹이 가장 낮은 사람(자신)의 양 옆 사람 중에서 자신과 랭크 차이가 적게 나는 사람과 경기를 치러야 한다.

랭크 차이가 많이 나는 사람과 경기를 치르게 되면 그 사람은 랭크차이가 많이 나는 만큼 경기를 더 많이 치러야 하기 때문이다. 경기를 더 많이 한다면 그만큼 최솟값과는 멀어질 수 밖에 없다.

 

가장 랭킹이 낮은 사람은 경기를 치르고난 후 사라진다.

그리고 남은 사람들 중 가장 랭킹이 낮은 사람을 찾아서 경기를 치르게 한다.

 

남은 사람이 1번 뿐이면 종료한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, maxidx, maxnum, ans;
vector<int> Rnk;
 
 
void input(){
    cin >> N;
    int a;
    
    for(int i = 0; i < N; i++){
        cin >> a;
        Rnk.push_back(a);
        if(a > maxnum){
            maxnum = a;
            maxidx = i;
        }
    }
}
 
void rank_diff(){
    if(maxidx - 1 >= 0 && maxidx + 1 < Rnk.size()){
        if(maxnum - Rnk[maxidx-1] < maxnum - Rnk[maxidx+1]){
            ans += (maxnum - Rnk[maxidx-1]);
        }
        else{
            ans += (maxnum - Rnk[maxidx+1]);
        }
    }
    else if(maxidx - 1 >= 0){
        ans += (maxnum - Rnk[maxidx-1]);
    }
    else if(maxidx + 1 < Rnk.size()){
        ans += (maxnum - Rnk[maxidx+1]);
    }
    
    Rnk.erase(Rnk.begin() + maxidx);
    maxnum--;
    
    for(int i = 0; i < Rnk.size(); i++){
        if(maxnum == Rnk[i]){
            maxidx = i;
            return;
        }
    }
}
 
void solve(){
    
    while(maxnum != 1){
        rank_diff();
    }
    
    cout << ans;
}
 
int main(){
    input();
    solve();
    
    return 0;
}