[그리디 알고리즘] 큰 수의 법칙 ★☆☆

---

문제

• N개의 숫자로 이루어진 배열에서 M개의 숫자를 더한 최댓값을 출력한다. 단, 하나의 숫자는 최대 K번 반복된다

 

입력 조건

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

출력 조건

• 첫째 줄에 답을 출력한다

 

입력 예시 1

5 8 3

2 4 5 4 6

 

출력 예시 1

46

---

이 문제를 해결하려면 가장 큰 수를 K번 더하고 그 다음 큰 수를 1번 더하는 방식으로 총 M번 더하면 된다

---

#include<bits/stdc++.h>
using namespace std;
int n, m, k;
int nmax, nxt;  // 최댓값, 최대 다음값
int num[1001];
int cnt;        // k번 반복 카운트
int ans;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 0; i < n;i++) {
        cin >> num[i];
        if (nmax <= num[i]) {
            nxt = nmax;
            nmax = num[i];
        }
    }
    for (int i = 0;i < m;i++) {
        if (cnt != k) {
            ans += nmax;
            cnt++;
            continue;
        }
        ans += nxt;
        cnt = 0;
    }
    cout << ans;
    return 0;
}

---

위 방식은 더할 때마다 M, cnt를 확인하는 방식이다

 

이것 말고도 처음부터 횟수를 계산한 뒤 한번에 계산하는 방법도 있다

 

M/K 번 동안 [max, max, ... , next] 수열이 반복될 것이고 그 이후 M-M/K 번 동안 max가 반복될 것이다

 

따라서 정답 ans는 (max*(K-1)+next) + (m-(m/k))*max 이다