[BOJ/백준][Gold4] 2262 : 토너먼트 만들기 (C++)

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

2262번: 토너먼트 만들기

 

 

[난이도] Gold4
[유형] Greedy

[풀이]
순위가 낮은 (숫자 큰) 사람을 빠르게 경기를 시켜서 빠르게 탈락시킬수록
랭킹의 차이의 합을 최소로 만드는데 유리하므로
경기를 매칭 시킬 때, 현재 남은 사람중에 랭킹이 가장 낮은 선수를 무조건 포함시켜 주는 방식으로
풀면 최적의 경우가 됩니다.

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,ans;
int main(){
    scanf("%d",&N);
    vector<int> v(N);
    for(int i=0;i<N;i++) scanf("%d",&v[i]);
    while(v.size()>1){
        int idx = max_element(v.begin(),v.end())-v.begin();
        int l=0,r=0;
        if(idx-1>=0) l=v[idx-1];
        if(idx+1<v.size()) r=v[idx+1];
        ans+=v[idx]-max(l,r);
        vector<int> tmp;
        for(auto c : v){
            if(c!=v[idx]) tmp.push_back(c);
        }
        v=tmp;
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2262.cpp