[백준] 2262번: 토너먼트 만들기(그리디)

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

2262번: 토너먼트 만들기

코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		//int[] arr = new int[n];
		List<Integer> list = new ArrayList<Integer>();
		int min = 0;
		
		for(int i=0; i<n; i++) 
			list.add(scan.nextInt());
			
		int max = n;	// 가장 랭킹이 낮은(숫자가 높은) 선수 
		for(int i=0; i<n-1; i++) {
			int idx = list.indexOf(max);	// 랭킹이 낮은 선수의 인덱스
			
			// 랭킹이 가장 낮은 선수가 가장 앞에 있을경우 => 그 뒤 선수와의 차이
			if(idx == 0)
				min += list.get(idx) - list.get(idx + 1);
			// 랭킹이 가장 낮은 선수가 가장 끝에 있을경우 => 그 앞 선수와의 차이
			else if(idx == list.size()-1) 
				min += list.get(idx) - list.get(idx -1);
			
			// 랭킹이 가장 낮은 선수가 중앙 어딘가에 있을경우 => 앞, 뒤 선수중 차이가 작은 선수와 매칭
			else
				min += Math.min(list.get(idx) - list.get(idx-1), list.get(idx) - list.get(idx+1));
			
			list.remove(idx);	// 랭킹이 가장 높은 선수는 매칭이 끝났으므로 제거,
			max --;
		}
		
		System.out.println(min);
		scan.close();
	}

}

풀이

두 선수의 랭킹 차이의 총 합의 최솟값을 구하는데 ..

논리는 다음과 같다.

 

랭킹이 낮은 선수(숫자가 큰 수)가 토너먼트에서 자주 올라갈수록 합은 크게 나온다.

따라서 랭킹이 낮은 선수부터 찾아서 매칭을 시킨다.

 

1. 랭킹이 가장 낮은 선수를 찾는다.(숫자가 가장 높은 선수)

 

2. 1.에서 찾은 선수와 좌, 우 선수와의 차이의 최솟값을 찾는다.

  2-1. 2에서 찾은 선수가 가장 왼쪽 => 그 선수의 오른쪽,

  2-1. 2에서 찾은 선수가 가장 오른쪽 => 그 선수의 왼쪽,

  2-1. 2에서 찾은 선수가 중앙 어딘가 => 그 선수의 왼쪽, 오른쪽과 비교

 

3. 랭킹이 가장 낮은 선수와 인접한 선수와의 최솟값을 구했으면, 랭킹이 가장 낮은 선수는 제거하고 그 다음으로 랭킹이 낮은 선수를 찾아 1~2의 과정을 반복한다.