[백준] 2262 토너먼트

0

백준

목록 보기
57/271
post-thumbnail

⚡백준 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;
}

📌참고자료

profile
Be able to be vulnerable, in search of truth

0개의 댓글