백준 27277번: 장기자랑

문제 설명

• https://www.acmicpc.net/problem/27277

접근법

• 가장 작은값 뒤에 가장 큰 값을 두는게 유리합니다.
  • 1 5 10 15를 예제로 살펴보겠습니다.
    순서를 바꾸지 않을 경우 첫번째 값을 제외하고 앞의 값에서 뒤의 값을 빼서 얻을 수 있는 점수의 합은 (5-1) + (10-5) + (15-10) = 14입니다.
    만약 순서를 바꿔 1 15 5 10으로 정렬한다면 (15-1) + (5-15) + (10-5) 인데 (5-15)는 0이 되어 최종적으로 19가 됩니다.
• N의 값이 홀수면 한명 남은 사람을 1번으로 진행하면 됩니다. N의 값이 짝수면 쌍으로 묶었을 때 앞의 값이 가장 큰 팀을 1번으로 진행하면 됩니다.
  • 1 5 10 15의 경우 (1,15), (5,10)이 짝을 이뤄 점수를 만들게 되고, 쌍들 중 앞의 값이 더 큰 (5,10)을 앞으로 두면 최종적으로 더 큰 값을 얻을 수 있습니다.

정답

import java.util.*;
import java.io.*;

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());
		StringTokenizer st = new StringTokenizer(br.readLine());
		List<Integer> lst = new LinkedList<Integer>();
		for (int i = 0; i < N; i++) {
			lst.add(Integer.parseInt(st.nextToken()));
		}
		Collections.sort(lst);
		int totalScore = 0;
		while(lst.size()>=2) {
			int min = lst.remove(0);
			int max = lst.remove(lst.size()-1);
			totalScore += Math.max(max-min,0);
            // N이 짝수였다면 min값이 가장 큰 쌍을 1번으로 정합니다.
			if(lst.size() == 0) {
				totalScore += min;
			}
		}
        // N이 홀수였다면 남은 값을 1번으로 정합니다.
		while(!lst.isEmpty()) {
			totalScore += lst.remove(0);
		}
		System.out.println(totalScore);
		
	}
}