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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWd7sgDatsMDFAUh

SW Expert Academy

 

그동안 K개 선별에 DFS를 사용했던 것은 선별되는 값 자체의 의미보다 그 값으로 다른 결과가 만들어지기 때문에 사용했던 것인데, 이번 문제는 그냥 최대값 K개를 뽑으면 되는 것이므로 DFS를 쓰면 시간초과가 발생한다.

그냥 sort를 통해 정렬 후 K값 선정. 중요한 것은 평균은 갈수록 큰 값과 진행 할 수록 최대이기때문에 

최대값 K개를 작은것부터 평균을 해서 진행하면 끝.

 

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;

vector<int> vec;


int N, K;
double maxa;


int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;

	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		vec.clear();
		maxa = 0;
		cin >> N >> K;
		for (int i = 0; i < N; i++)
		{
			int m;
			cin >> m;
			vec.push_back(m);
		}

		sort(vec.begin(), vec.end());
		double A = 0.0;
		for (int i = N - K; i < N; i++)
		{
			A = (A + vec[i]) / 2;
		}
		
		

		cout << "#" << test_case << " " << A << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}