백준 - 2262번 : 토너먼트 만들기 (C++)

풀이 방법 : 그리디

랭킹이 높은 사람이 무조건 이기고 입력값은 랭킹은 1 ~ N까지 주어진다고 했기 때문에 결국에는 무조건 1위가 우승을 한다.
그렇다면 제일 낮은 순위의 사람을 가능한 최소한의 차로 경기를 진행하도록 하면 자연스럽게 랭킹차의 합이 최소화될 것이다.

그렇기 때문에 현재 남아있는 사람들중 랭킹이 가장 낮은 사람을 찾아 그 사람의 앞 뒤 중 랭킹차가 적게나는 쪽을 선택해서 합계에 더해주고 랭킹이 가장 낮은 사람을 vector에서 지워주는 형식으로 처리해주었다. vector의 size가 1이 되는 순간 루프를 종료한다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	vector<int> vecPlayer(N);

	int Sum = 0;

	for (int i = 0; i < N; ++i)
	{
		cin >> vecPlayer[i];
	}

	while (true)
	{
		int Size = vecPlayer.size();

		if (Size == 1)
			break;

		int Idx = 0;
		int LowestRank = 0;

		for (int i = 0; i < Size; ++i)
		{
			if (vecPlayer[i] > LowestRank)
			{
				Idx = i;
				LowestRank = vecPlayer[i];
			}
		}

		int Minus = 257;
		if (Idx + 1 < Size)
		{
			Minus = min(abs(vecPlayer[Idx] - vecPlayer[Idx + 1]), Minus);
		}

		if (Idx - 1 >= 0)
		{
			Minus = min(abs(vecPlayer[Idx] - vecPlayer[Idx - 1]), Minus);
		}
		
		vecPlayer.erase(vecPlayer.begin() + Idx);
		Sum += Minus;
	}

	cout << Sum;

}