[백준/BOJ] 2262. 토너먼트 만들기 [Gold 5]

2262. 토너먼트 만들기

문제출처 : https://www.acmicpc.net/problem/2262

code

#include <iostream>
using namespace std;

int main()
{
    int n, i, j, arr[257] = { 0 }, temp[257] = { 0 }, result = 0;

    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> arr[i];
   
    for (i = n; i > 1; i--)
    {
        for (j = 1; j <= n; j++)
        {
            if (arr[j] == i)
            {
                if (arr[j - 1] < arr[j + 1])
                {
                    result += arr[j] - arr[j + 1];
                    arr[j] = arr[j + 1];
                    break;
                }
                else
                {
                    result += arr[j] - arr[j - 1];
                    arr[j] = arr[j - 1];
                    break;
                }
            }
        }
        
        int k = 1;
        for (j = 1; j <= n; j++)
        {
            if (arr[j] == arr[j - 1])
                continue;

            temp[k] = arr[j];
            arr[k] = temp[k];
            k++;
        }
        arr[i] = 0, temp[i] = 0;
    }
    cout << result;

    return 0;
}

정렬도안들어가고 구현도 아니고 진짜 순수 그리디알고리즘 문제였다.
랭킹의 차이가 최소가 되려면 랭킹이 낮은 사람들은 일찍 시합을 하는게 유리하다.
그러니까 랭킹이 가장낮은사람의 양옆을 비교해서 랭킹이 낮은사람을 골라 붙이고, 그다음 낮은사람의 양옆을 비교해서 랭킹이 낮은 사람을 골라 붙이고 이걸 반복하면 최소값이 나올것이다.