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

문제 >

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

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

예를 들어 추첨 결과가 차례로 랭킹 1, 6, 2, 5, 3, 4위의 선수들이었을 때의 토너먼트 세 개가 위에 있다. <A>의 경우는 각 시합이 (1 6), (2 5), (3 4), (1 2), (1 3)으로 랭킹 차이의 합이 5+3+1+1+2=12가 된다. 반면에 <B>는 11이, <C>는 10이 된다.

토너먼트 추첨 결과가 주어졌을 때, 각 시합에 임하는 두 선수의 랭킹 차이의 총 합의 최솟값을 구하는 프로그램을 작성하시오.

 

입력 >

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

출력 >

첫째 줄에 답을 출력한다.

 

해결방법 > 

그리디 알고리즘으로 해결

 

랭킹이 가장 낮은 선수부터 찾고 좌 우 선수 중 랭킹 차이가 적은 선수와 시합 하도록 한다.

 

1 6 2 5 3 4 (6 - 2 = 4)

1 2 5 3 4 (5 - 3 = 2)

1 2 3 4 (4 - 3 = 1)

1 2 3 (3 - 2 = 1)

1 2 (2 - 1 = 1)

 

[C++]

#include <iostream>
#include <vector>

using namespace std;
//solution : 가장 큰 값부터 제거해나감
int main(){
    int n;
    int sum = 0;
    vector <int> v;
    cin >> n;

    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    

    for(int i = 0; i < n-1; i++){
        int size = n - i;
        int max = 0;
        int idx;
        int dif;
        
        for(int j = 0; j < size; j++){
            if(max < v[j]){ //가장 큰 값을 탐색
                max = v[j];
                idx = j;
            }
        }

        if(idx == 0)
            dif = abs(v[idx] - v[idx+1]); //제일 큰 수가 첫번째 인덱스일 때
        else if(idx == size - 1) 
            dif = abs(v[idx-1] - v[idx]); //제일 큰 수가 두번째 인덱스일 때
        else{
            int tmp_idx = (v[idx-1] > v[idx+1])? idx-1 : idx+1;
            dif = abs(v[idx] - v[tmp_idx]); //가장 큰 값 양 옆의 값 중 차이가 적은 값 선택
        }

        sum += dif;

        //가장 큰 값 삭제
        for(int j = idx; j < size - 1; j++){
            v[j] = v[j + 1];
        }
    }
    cout << sum;
}

 

[JAVA]

package baekjoon;

import java.util.*;

public class BOJ_2262 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		ArrayList <Integer> list = new ArrayList();
		int diff = 0;
		
		for(int i = 0; i < n; i++) {
			int tmp = sc.nextInt();
			list.add(tmp);
		}
		
		int max = n;
		for(int i = 0; i < n - 1; i++) {
			int idx = list.indexOf(max);
			if(idx == 0) {
				diff += list.get(idx) - list.get(idx + 1);
			}
			else if(idx == list.size() - 1)
				diff += list.get(idx) - list.get(idx - 1);
			else
				diff += Math.min(list.get(idx) - list.get(idx + 1), list.get(idx) - list.get(idx - 1));
			list.remove(idx);
			max--;
		}
		System.out.println(diff);
	}
}

 

문제링크 >

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

2262번: 토너먼트 만들기