[백준 - 2262][GOLD 4][해설 X] - 토너먼트 만들기 (JAVA)

문제 링크

---

https://www.acmicpc.net/problem/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까지의 자연수로 나타나며, 랭킹이 같은 경우는 없다고 가정하자.

 

출력

---

첫째 줄에 답을 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        List<Integer> tournament = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0;i<N;i++){
            tournament.add(Integer.parseInt(st.nextToken()));
        }

        long sum = 0;
        int maxTarget = N;
		
        //가장 큰 숫자를 매번 찾아 없앤다.
        while(tournament.size() > 1){
            int idx = tournament.indexOf(maxTarget);
			
            //가장 왼쪽에 있는경우
            if(idx == 0){
                sum += Math.abs(tournament.get(idx) - tournament.get(idx+1));
            }
            //가장 오른쪽에 있는 경우
            else if(idx == tournament.size()-1){
                sum += Math.abs(tournament.get(idx) - tournament.get(idx-1));
            }
            //나머지 경우
            else{
                sum += Math.min(Math.abs(tournament.get(idx) - tournament.get(idx-1)),Math.abs(tournament.get(idx) - tournament.get(idx+1)));
            }

            tournament.remove(idx);
            maxTarget--;
        }

        System.out.println(sum);
    }
}

 

 

실행 결과

---

 

 

팁

---

• 어쩔때 가장 최소일지 판단하려면 가장 큰수, 가장 작은수를 기준으로 하나씩 다음 단계로 진행해보자