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

SWExpertAcademy의 성수의 프로그래밍 강좌 시청(6719 / D4) 문제이다.

[ 문제풀이 ]

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

문제에서 제시한 실력을 구하는 공식에 / 2 가 있기 때문에, 가장 먼저 들은 강의일수록 숫자가 더 작아질 것이다.

강의를 5개를 듣는다고 가정했을 때, 첫 번째로 듣는 강의는 / 2 를 5번을 거치게 된다. 반면에 마지막에 듣는 강의의 경우

/ 2 를 한번만 거치면 된다. 그래서 본인은 가장 수준이 높은 강의가 2로 나눠지는 횟수를 최소화 시키기 위해서

수준이 높은 강의일수록 마지막쪽에 들을 수 있도록 구현하였다.

따라서, 강좌를 오름차순으로 정렬 후에, 뒤에서 K개 만큼을 순차적으로 듣도록 구현하였다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 10010
using namespace std;
 
int N, K;
int Lecture[MAX];
double Answer;
 
void Initialize()
{
    Answer = 0;
}
 
void Input()
{
    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> Lecture[i];
}
 
void Solution()
{
    sort(Lecture, Lecture + N);
    for (int i = N - K; i < N; i++)
    {
        Answer = (Answer + Lecture[i]) / 2;
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout << fixed;
    cout.precision(6);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}