[C++] 백준 2262번 토너먼트 만들기

문제

월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러도 랭킹이 높은 사람이 반드시 이기게 된다. 따라서 월드시에서는 게임을 흥미진진하게 만들기 위해서, 부전승을 여러 번 만들더라도 각 시합에 임하는 선수들의 랭킹 차이를 비슷하게 만들려고 한다.

토너먼트를 만들 때에는 이미 추첨이 된 순서대로 선수들을 배치하고, 왼쪽에서 오른쪽의 순서가 어긋나지 않도록 시합을 정한다. 물론 부전승을 임의로 만들 수 있지만, 토너먼트가 꼬여서는 안 된다. 또한, 각 시합에 임하는 두 선수의 랭킹의 차이의 합이 최소가 되도록 하려 한다.

예를 들어 추첨 결과가 차례로 랭킹 1, 6, 2, 5, 3, 4위의 선수들이었을 때의 토너먼트 세 개가 위에 있다.
<
토너먼트 추첨 결과가 주어졌을 때, 각 시합에 임하는 두 선수의 랭킹 차이의 총 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 n(1≤n≤256)이 주어진다. 다음 줄에는 추첨 결과를 나타내는 n명의 선수들의 랭킹이 주어진다. 각 선수의 랭킹은 1부터 n까지의 자연수로 나타나며, 랭킹이 같은 경우는 없다고 가정하자.

출력

첫째 줄에 답을 출력한다.

풀이

랭킹이 높은(숫자가 작은)선수가 항상 이기므로 숫자가 작은 선수를 먼저 경기하게해야 랭킹의 차이가 최소가 된다.
vector의 내장함수인 erase()를 사용후 it의 값이 사라진다는 점만 주의하면 구현하는 것은 어렵지 않다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int n,num = 0;
vector<int> arr;

int solve(){
  int ans = 0;

  // n-1번 경기해야 1등 나옴
  for (int i=n; i>=2; i--){
    vector<int>::iterator it = arr.begin();

    while (*it != i){
      it++;
    }

    // i등이 맨 처음에 위치
    if (it == arr.begin()){
      it = arr.erase(it);
    }
    // i등이 맨 끝에 위치
    else if (it == arr.end()-1){
      arr.erase(it);
      it = arr.end()-1;
    }
    else {
      // 왼쪽이랑 붙을경우
      if (*(it-1) > *(it+1)){
        it = arr.erase(it);
        it--; 
      }
      // 오른쪽이랑 붙을경우
      else{
        it = arr.erase(it);
      }
    }
    ans += i-*it;
  }
  return ans;
}

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

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n;

  for (int i=0; i<n; i++){
    int a;
    cin >> a;
    arr.push_back(a);
  }
  
  cout << solve();
}