[SWEA] 6719 성수의 프로그래밍 강좌 시청

문제 출처: SW Expert Academy

SW Expert Academy

: 프로그래밍 강좌의 전체 개수와 들을 수 있는 개수가 주어진다.

: 각각의 강좌 수준이 주어지고, 강좌를 들으면 해당 강좌의 수준과 현재 실력과의 평균값이 현재 실력이된다.

: 또한 프로그래밍 강좌를 듣는 순서는 강제되어 있지 않다.

: 처음에는 모든 조합을 고려하도록 코드를 작성했다.

→ 이 경우 시간 초과가 난다.

: 다시 생각해 본 결과 강좌를 듣는 순서가 자유이기 때문에 강좌의 수준을 오름차순으로 정렬하고

: 들을 수 있는 강좌의 수 만큼 뒤에서부터 오름차순으로 접근하는 그리디적인 방법을 생각하게 되었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Solution {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int N, K;
    static int[] arr, selected;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        // 테스트 케이스 수를 입력받고
        int T = Integer.parseInt(br.readLine());
 
        // 테스트 케이스 수만큼 반복하며
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            // N과 K를 입력받아
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
 
            // N사이즈의 전체 배열과
            arr = new int[N];
            // K사이즈의 선택된 배열을 만들어
            selected = new int[K];
 
            // 전체 배열을 입력받고
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++)
                arr[i] = Integer.parseInt(st.nextToken());
 
            // 정렬시켜서 큰 수부터 K를 작은 순서대로 더해가며 평균을 구해줌
            double max = 0;
            Arrays.sort(arr);
            for(int i = K; i > 0; i--) {
                max = (max+arr[N-i])/2;
            }
            sb.append(String.format("#%d %f\n", tc, max));
        }
        System.out.println(sb);
    }
 
}