Algorithm

[027] 20115. 에너지 드링크

JEE-JEEE 2024. 3. 11. 14:07

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

 

20115번: 에너지 드링크

페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다. 야근을 마치고 한

www.acmicpc.net

 


 

💡풀이

 간단한 비교-선택 문제로, 간단하게 계속해서 기존에 있는 것과 새 것을 비교하여 연산을 수행, 제시된 수열이 없어질 때까지 반복하는 문제이다. 스택을 사용하면 간단하게 풀이가 가능하다.

 

최대로 하기 위해서는 무조건 큰 값과 작은 값을 비교해 작은 값을 반으로 나누는 것이 유리하기 때문에, 우선 들어온 수를 오름차순으로 정렬하고, 처음이라면 제일 마지막에 있는 값(Deque는 양 끝에서 추출이 가능하다) 을 가져와서 제일 첫번째 값과 비교한다. 다음부터는 현재 가지고 있는 값과 다음 값을 비교하는 연산을 연속적으로 수행하고, 덱이 전부 빈 순간 끝내면 된다. 정수일 경우는 정수로 표현하고, 실수일 경우에는 실수의 형태로 표현해야 하기 때문에 마지막에 이것이 정수인지 실수인지 평가하는 것까지 포함했다.

 

package list;

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

public class Q20115 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        int n = Integer.parseInt(br.readLine());
        Deque<Integer> deq = new ArrayDeque<>();
        PriorityQueue<Integer> que = new PriorityQueue<>();
        int[] nums = new int[n];

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

        for(int i = 0; i < n; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(nums);

        for(int num : nums){
            deq.add(num);
        }

        double fin = 0;
        int intFin = 0;

        while(!deq.isEmpty()){

            // 제일 앞의 값을 뺌
            double fst = deq.pollFirst();

            // fin이 0이라면 첫번재 순서니까 제일 뒤랑 비교
            if(fin == 0){
                double last = deq.pollLast();
                fin = (fst/2) + last;

            // 아니라면 fin과 fst를 비교해서 작은 값 % 2
            }else{

                fin = (fst > fin) ? (fin/2) + fst : (fst/2) + fin;
            }

        }

        intFin = (int) fin;
        if((double)intFin == fin){
            bw.write(String.valueOf(intFin));
        }else{
            bw.write(String.valueOf(fin));
        }




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