boj 2262 토너먼트 만들기

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

2262번: 토너먼트 만들기

주어지는 랭킹은 중복이 없으며, 랭킹이 높은 사람 (숫자가 낮은 사람)이 무조건 이깁니다.

문제에서 요구하는 것은 이 토너먼트에서 각 경기에 임하는 선수들의 랭킹의 차이의 합이 최소가 되도록 대진을 구성해야합니다.

 

랭킹이 낮을수록 (숫자가 클수록) 랭킹의 차이의 합이 커지므로 랭킹이 낮은 선수는 빠르게 경기를 하는 것이 이득입니다.

따라서 랭킹이 낮은 선수부터 차례대로 본인의 좌우 선수들 중 랭킹이 낮은 선수와 경기를 하게 만들면 랭킹의 차이의 합이 최소가 됩니다.

 

 

#include <iostream>
#include <algorithm>
#define MAX 256
using namespace std;
 
int list[MAX];
int N;
 
void func() {
    int ans = 0;
    for (int i = N; i > 1; i--) {
        int j = 0;
        for (; j <= N; j++) {
            if (i == list[j]) break;
        }
 
        ans += (i - max(list[j - 1], list[j + 1]));
 
        for (; j < N; j++) {
            list[j] = list[j + 1];
        }
        N--;
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}