코테/Greedy
[C/C++] 나동빈 가장 큰 수 만들기, Greedy
상똥
2023. 2. 2. 13:01
문제
다양한 숫자들로 구성된 배열이 있을 때, 주어진 수를 M번 더하여 가장 큰 수를 만들되, 해당 숫자의 인덱스에 해당하는 수가 연속 K번 초과하여 더해질 수 없다. 예시1) N={2, 4, 5, 4, 6}, M=8, K=3 정답: 6+6+6+5+6+6+6+5=46 예시2) N={3, 4, 3, 4, 3}, M=7, K=2 정답: 4+4+4+4+4+4+4=28 첫 번째 줄에 배열의 크기 N(2≤N≤1,000), M(1≤M≤10,000), K(1≤K≤10,000)의 자연수가 주어지며 각 자연수는 공백으로 구분한다. 두 번째 줄에 자연수인 배열의 원소가 주어지며 각 원소는 공백으로 구분한다. K는 항상 M보다 작거나 같아야 한다. |
코드
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<int> arr;
int N, M, K, t;
cin >> N >> M >> K;
for (int i = 0; i < N; i++) {
cin >> t;
arr.push_back(t);
}
sort(arr.begin(), arr.end());
int F = arr[N - 1], S = arr[N - 2];
int c = M / (K + 1);
int sum = c * (K * F + S) + (M - c1 * (K + 1)) * F;
cout << sum;
return 0;
}
풀이
1. vector 를사용하여 배열을 입력받는다.
2. algorithm을 사용하여 배열을 오름차순으로 정렬한다.
3. 가장 큰 수를 K번, 두 번째로 큰 수를 한 번 더하는 과정을 반복하므로 각각을 F=num[N-1], S=num[N-2]로 저장한다.
4. 가장 큰 수가 M번, 두 번째로 큰 수가 한 번 반복되는 성질을 수열에 대입하여 연산으로 프로그래밍한다.