[백준] 2262 토너먼트

⚡백준 2262 토너먼트

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

• 랭킹이 낮은 선수는 어차피 우승하지 못한다
  -> 랭킹이 낮은 선수부터 경기시켜 토너먼트에서 제외시키며 토너먼트를 만들면 된다
  -> 가장 랭킹이 낮은 선수를 찾아서 그 선수의 양쪽 중에 랭킹 차가 더 작은 사람과 경기를 진행한다

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	vector<int> tournament;
	
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int input;
		cin >> input;
		tournament.push_back(input);
	}

	int sum = 0;
	for (int worst = n; worst > 1; worst--) {
		for (auto it = tournament.begin(); it != tournament.end(); ++it) {
			if (*it == worst) {
				//토너먼트의 맨 왼쪽
				if (it == tournament.begin()) {
					int right = *(it + 1);

					sum += abs(worst - right);
					tournament.erase(it);
					break;
				}
				//토너먼트의 맨 오른쪽
				else if (it == tournament.end() - 1) {
					int left = *(it - 1);

					sum += abs(worst - left);
					tournament.erase(it);
					break;
				}
				//토너먼트의 중간
				else {
					int right = *(it + 1);
					int left = *( it - 1);

					sum += min(abs(worst - right), abs(worst - left));
					tournament.erase(it);
					break;
				}
			}
		}
	}

	cout << sum;
	return 0;
}

📌참고자료

• 백준 2262 토너먼트 풀이
  https://velog.io/@langssi/%EB%B0%B1%EC%A4%80-2262-%ED%86%A0%EB%84%88%EB%A8%BC%ED%8A%B8-%EB%A7%8C%EB%93%A4%EA%B8%B0