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

성수는 이제 프로그래밍을 시작하기로 마음 먹은 초보다.

그렇기에 프로그래밍 강좌를 통해 자신의 프로그래밍 실력을 끌어 올리려고 한다.

성수의 실력이 A라고 할 때, 수준이 M인 강좌를 시청하고 나면 성수의 실력은 (A+M)/2가 된다.

즉, 성수는 자신이 보는 강좌가 좋은 지 아닌지 판단하지 않고 그대로 강좌를 받아들이기 때문에,

실력보다 낮은 수준의 강좌를 보면 실력이 낮아질 수 있다.

현재 성수는 아직 아무런 실력이 없다. 즉 실력이 0이다.

성수는 볼 수 있는 강좌 총 N개 찾았고 시간 문제상 이 중에서 K개를 적절한 순서로 선택해 한 번씩 시청하려고 한다.

성수가 같은 강좌를 두 번 이상 보는 일은 없다고 할 때, 성수가 가질 수 있는 실력의 수치는 최대 몇인지 구하는 프로그램을 작성하라.

 

이 문제의 경우 N개중에서 K개를 골라 시청하였을때 실력의 최대 수치를 구해야하는 것이다.

 

1. 현재실력은 0 => 초기 값은 0으로 시작하고

2. K개를 적잘한 순서로 선택해 한 번씩 시청한다. => 순서가 중요하다.

 

이 경우 생각해보면 순서가 중요하다고 할 수 있는데 예시를 들어서

 

현재 0, 주어진 강좌 1과 9이고 두 강좌 모두 듣는다고 하였을때

 

1. ( ( 0 + 1) / 2 + 9 ) / 2 = 4.75

2. ( ( 0 + 9) / 2 + 1 ) / 2 = 2.75

 

로 나오게 되는데 식만 보더라도 처음에 나온 수는 뒤로 갈 수록 2로 나누어지는 경우가 많아짐으로 큰 수는 나중에 더 하는 것이 유리하다는 것을 알 수 있다.

 

그리고 두 강좌중 하나만 듣는 다고 가정 하였을 때 물론 9를 듣는 것이 누가 봐도 좋아 보인다. 

 

결론, 최대한 큰 숫자들을 듣고 가능하다면 오름차순으로 듣도록 하자.

 

이를 코딩으로 나타내면 오름차순으로 sort를 하고 N개가 있다면 N-K 부터 N 개 까지의 수를 시청한다면 실력이 최대가

 

될 수 있다.

 

최종 코드는 다음과 같다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Solution {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		int N = 0;
		int K = 0;
		double result = 0;
		String[] s = null;
		int[] arr = null;
		for(int t=1; t<=T; t++) {
			result = 0;
			s = br.readLine().split(" ");
			N = Integer.parseInt(s[0]);
			K = Integer.parseInt(s[1]);
			s = br.readLine().split(" ");
			arr = new int[N];
			for(int i=0; i<N; i++) {
				arr[i] = Integer.parseInt(s[i]);
			}
			Arrays.sort(arr);
			for(int i=arr.length-K; i<arr.length; i++) {
				result = (result+arr[i])/2;
			}
			bw.write("#"+t+" "+result+"\n");
		}
		br.close();
		bw.close();
	}
}