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

문제

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

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

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

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

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

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

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

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

 

풀이방법

그리디 알고리즘으로 문제를 해결한다.

 

성수의 실력을 가장 많이 늘릴 수 있는 방법은 ,

 

N개의 강좌 중 가장 높은 K개의 강좌를 고르고, 이 중에서 낮은 순서대로 강좌를 듣는 것이다.

 

소스코드

package samsung;

import java.util.*;

public class s_6719 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			int n = sc.nextInt();
			int k = sc.nextInt();
			double r = 0;
			ArrayList <Integer> a = new ArrayList<>();
			for(int i = 0; i < n; i++) {
				int tmp = sc.nextInt();
				a.add(tmp);
			}
			
			Collections.sort(a);
			
			for(int i = a.size() - k; i < a.size(); i++) {
				r = (r + a.get(i)) / 2;
			}
			System.out.printf("#%d %.6f\n", t, r);
		}
	}
}