[그리디] 큰 수의 법칙

실전 문제 1. 큰 수의 법칙

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

예를 들어 순서대로 2,4,5,4,6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46이 된다.

단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.

입력 조건

첫째 줄에 N, M, K의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다.
K는 항상 M보다 작거나 같다.
5 8 3
2 4 5 4 6

출력 조건

46

간단 구현

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int n, m, k, x, sum = 0;
	cin >> n >> m >> k;
	vector<int> v;

	for (int i = 0; i < n; i++)
	{
		cin >> x;
		v.push_back(x); 
	}
	sort(v.rbegin(), v.rend()); //내림차순 정렬
	int first = v[0]; //가장 큰 수 저장
	int second = v[1]; // 두번째로 큰 수 저장
	while (1)
	{
		for (int i = 0; i < k; i++)
		{
			if (m == 0)
				break;
			sum += first;
			m--;
		}
		if (m == 0)
			break;
		sum += second;
		m--;
	}
	cout << sum;
}

반복되는 수열

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int n, m, k, x, sum = 0;
	cin >> n >> m >> k;
	vector<int> v;

	for (int i = 0; i < n; i++)
	{
		cin >> x;
		v.push_back(x); 
	}
	sort(v.rbegin(), v.rend()); //내림차순 정렬
	int first = v[0]; //가장 큰 수 저장
	int second = v[1]; // 두번째로 큰 수 저장
	
	int cnt = int(m / (k + 1)) * k;
	cnt += m % (k + 1);

	sum += (cnt)*first;
	sum += (m - cnt) * second;
	cout << sum;
}