백준 20300 서강근육맨 문제풀이 (JAVA)

링크텍스트

문제

로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.
헬스장에 있는 N개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지 않았던 운동기구를 선택하기로 계획을 세웠다. 그리고 비용을 절약하기 위해 PT를 받을 때 운동기구를 되도록이면 두 개를 사용하기로 했다. 예를 들어, 헬스장에 총 10의 운동기구가 있을 경우 PT를 5번 받으면 모든 기구를 다 사용할 수 있다. 9개의 운동기구가 있는 경우에도 PT를 5번 받지만, 마지막 PT를 받을 때는 운동기구를 하나만 사용한다.

하지만 향빈이는 운동기구를 선택하다가 큰 고민에 빠졌다. 왜냐하면 운동기구마다 근손실이 일어나는 정도가 다르기 때문이다. 어떤 운동기구는 자극이 잘 안 와서 근손실이 적게 일어나는데, 어떤 운동기구는 자극이 잘 와서 근손실이 많이 일어난다. 근손실이 죽음보다 무서운 향빈이는 PT를 한 번 받을 때의 근손실 정도가 M을 넘지 않도록 하고 싶다. 이때, M의 최솟값을 구해보자. 참고로, 운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.

입력

입력

첫째 줄에 서강헬스클럽에 비치된 운동기구의 개수를 나타내는 정수 N이 주어진다. (1<=N<=10000)

둘째 줄에는 각 운동기구의 근손실 정도를 나타내는 정수 t1, t2, t3 ... tn이 주어진다.(0<=tn<=10^18)

출력

M의 최솟값을 출력한다.

풀이

각 운동기구의 근손실 정도를 입력받은 후 오름차순으로 정렬한다.
만약 운동기구가 홀수라면 N번째 운동기구는 제일 근손실이 크디 한 개로만 하고, 나머지는 가장 큰 손실 + 가장 작은 손실로 해서 각 손실간 차이를 최소로 시킨다.

소스코드

import java.text.DecimalFormat;
import java.util.*;
import java.io.*;

//import java.math.BigInteger;
public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        final int NUMBER_OF_FITNESS = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        long fitness[] = new long[NUMBER_OF_FITNESS];
        for (int i = 0; i < NUMBER_OF_FITNESS; i++) {
            fitness[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(fitness);
        long lossMax = Long.MIN_VALUE;
        if (NUMBER_OF_FITNESS % 2 == 1) {
            lossMax = fitness[NUMBER_OF_FITNESS - 1];
            for (int i = 0; i < (NUMBER_OF_FITNESS - 1) / 2; i++) {
                long loss = fitness[i] + fitness[NUMBER_OF_FITNESS - 2 - i];
                if (loss > lossMax) {
                    lossMax = loss;
                }
            }
        } else {
            for (int i = 0; i < NUMBER_OF_FITNESS / 2; i++) {
                long loss = fitness[i] + fitness[NUMBER_OF_FITNESS - 1 - i];
                if (loss > lossMax) {
                    lossMax = loss;
                }
            }
        }
        sb.append(lossMax);
        sb.append("\n");

        bw.write(sb.toString());

        bw.flush();
        br.close();
        bw.close();

    }


}