<CodingStudy>Greedy1

이것이 코딩테스트다 큰 수의 법칙 실전 문제

 

'큰 수의 법칙'은 m번 더하여 가장 큰 수를 만드는 법칙이며, K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

입력조건:

첫째 줄에N(2<=N<=1,000),M(1<=M<=10,000),K(1<=K<=10,000)의 자연수가 주어지며 각 자연수는 공백으로구분
둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다 단, 각각의 자연수는 1이상 10,000이하의 수로 주어진다. 입력으로 주어지는 K는 항상 M보다 작겉나 같다.

 

출력조건:

주어진 수들의 M번을 더하여 가장큰수를 만드는것이며 K번을 초과하여 더해질 수 없다.

입력예시 :
5 8 3
2 4 5 4 6
출력예시:46

 

#include <iostream>
using namespace std;


int main()
{
	int N, M, K;
	int a[1000];
	int max= 0;
	int result = 0;
	int second = 0;
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
	}

	for (int i = 0; i < N; i++)
	{
		if (max < a[i])
		{
			max = a[i];
		}
	}
	for (int i = 0; i < N; i++)
	{
		if (a[i] != max)
		{
			if (second < a[i])
			{
				second = a[i];
			}
		}
	}

	while (M != 0)
	{
		for (int i = 0; i < K; i++)
		{
			result += max;
			--M;
		}
		if (max == second)
		{
			for (int i = 0; i < K; i++)
			{
				result += max;
				--M;
			}
		}
		
		else
		{
			result += second;
			--M;
		}
	}
	cout << result;
}