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

풀이 아이디어

가지고 있는 에너지 드링크의 수를 n이라고 하고
드링크 양을 저장한 리스트 int[n] drinks를 오름차순으로 정렬한다.
그러면 drinks[n-1]이 최대량인 드링크가 되는데 옮겨서 붓는 과정에서 양이 절반이 되므로
제일 양이 많은 드링크에 나머지 드링크들을 부어야 최대양인 하나의 드링크가 완성된다.
이 과정에서 드링크의 양이 716.5 같은 실수도 나올 수 있으므로 double타입으로 선언해준다.

문제 조건에 절대/상대 오차는 10-5까지 허용한다고 적혀있다.
즉, 20.0 같은 것도 20으로 쳐준다는 의미라서 형변환만 잘해주면 상관없다.

풀이 코드

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

public class _20115 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] drinks = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            drinks[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(drinks); // 오름차순 정렬
        
        double sumDrink = (double)drinks[n-1]; // 제일 큰 음료수는 그대로 더해준다.
        // 제일 양이 적은 드링크부터 2번째로 많은 드링크까지 순회하며 합산
        for(int i=0;i<n-1;i++){
            sumDrink += drinks[i]/2.0;
        }
        System.out.println(sumDrink);
    }
}

성능 개선한 풀이 코드

더 성능을 개선할 수 있을 것 같아서 코드를 한 번 깎아보았다.
위에 방식은 정렬하고 모든 에너지드링크를 나누기 2를 해줬었는데
모든 에너지드링크를 총량을 저장하는 변수 double sumDrink에
모든 드링크 양을 더해주고 가장 양이 많은 드링크 양을 저장한 변수 maxDrink 한번 더 더한 뒤에
전체를 나누기 2를 해주면 -> (sumDrink+maxDrink)/2 해주면
maxDrink를 제외한 나머지 드링크의 양은 절반이고
maxDrink는 2번 더한 다음에 절반이므로 원래 양이 된다. / 연산 한 번에 계산가능하다.

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

public class _20115 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        double n = Integer.parseInt(br.readLine());
        double sumDrink = 0, maxDrink = 0, currentDrink = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            currentDrink = (double)Integer.parseInt(st.nextToken());
            if( maxDrink < currentDrink){
                maxDrink = currentDrink;
            }
            sumDrink += currentDrink;
        }
        System.out.println((sumDrink+maxDrink)/2);
    }
}