문제 설명
배열 arr[]과 두 정수 M, K가 주어졌을 때, 주어진 배열의 원소들만을 사용해 새로운 배열을 만드는 것이 목표입니다. 이때 반드시 지켜야 할 조건은 다음과 같습니다.
- 새 배열의 크기는 정확히 M이어야 합니다.
- 크기가 K보다 큰 어떤 부분 배열(sub-array)도 모든 원소가 동일해서는 안 됩니다.
최종적으로 위 조건을 만족하면서 만들 수 있는 배열의 최대 합을 출력해야 합니다.
예시
입력: arr[] = {1, 2, 4, 5, 7}, M = 5, K = 2
설명: 조건을 만족하는 배열은 {7, 7, 5, 7, 7}입니다. 이 배열에는 크기가 2를 초과하면서 모든 원소가 같은 부분 배열이 존재하지 않습니다.
접근 방법
합을 최대화하려면 당연히 가장 큰 값을 최대한 많이 사용해야 합니다. 하지만 최댓값을 K번 연속으로 배치할 수 없으므로, K번마다 두 번째로 큰 값을 한 개씩 끼워 넣어야 합니다.
즉, "K개의 최댓값 + 1개의 두 번째 최댓값" 패턴을 반복해 길이가 M인 배열을 구성하면 됩니다. 전체 길이 M 중에서 두 번째 최댓값이 들어가는 자리의 개수는 M / (K + 1)이므로, 최종 합은 아래 식으로 간단히 계산할 수 있습니다.
(M / (K + 1)) * max2 + (M - M / (K + 1)) * max1
C++ 구현 예제
#include <iostream>
using namespace std;
long int arraySum(int arr[], int n, int m, int k){
int max1 = arr[0], max2 = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max1) {
max2 = max1;
max1 = arr[i];
}
else if (arr[i] > max2)
max2 = arr[i];
}
int max2count = m / (k + 1);
long int sum = max2count * max2 + (m - max2count) * max1;
return sum;
}
int main() {
int arr[] = { 1, 3, 6, 7, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int m = 9, k = 2;
cout<<"The maximum sum of array created from the given array such that no subarray of size greater than "<<k<<" will have same elements is ";
cout<<arraySum(arr, n, m, k);
return 0;
}
실행 결과
The maximum sum of array created from the given array such that no subarray of size greater than 2 will have same elements is 60
동작 원리 정리
- 배열을 한 번 순회하며 최댓값(max1)과 두 번째 최댓값(max2)을 찾습니다.
- 두 번째 최댓값이 들어갈 자리의 개수를 m / (k + 1)로 계산합니다.
- 나머지 자리는 모두 최댓값으로 채운다고 가정하고 전체 합을 구합니다.
이 알고리즘은 배열을 한 번만 순회하면 되므로 시간 복잡도가 O(n)으로 매우 효율적입니다.