이 문제에서는 정수 배열 arr[]과 숫자 k가 주어지며, 크기가 k인 부분 수열(subsequence) 중에서 원소들의 곱이 가장 커지는 값을 찾는 프로그램을 C++로 작성하는 것이 목표입니다.
문제 설명
주어진 배열에서 크기가 k(1 ≤ k ≤ n)인 부분 수열을 선택했을 때, 그 원소들을 모두 곱한 값이 최대가 되는 경우를 구해야 합니다.
예제로 이해해 보기
입력
arr[] = {1, 5, 6, -2, 0, 4} , k = 3출력
120
설명
크기가 3인 부분 수열 중 곱이 가장 큰 것은 (5, 6, 4)이며, 그 곱은 120입니다.
해결 접근 방법
이 문제를 풀기 위해서는 먼저 배열 arr[]을 정렬한 뒤, 배열의 원소 값과 k의 값에 따라 방법을 달리 적용해야 합니다. 다음과 같은 경우로 나누어 생각할 수 있습니다.
경우 1: k가 짝수인 경우
결괏값은 0을 제외한 가장 큰 k개의 값으로 구성할 수 있습니다. 단, 음수 두 개를 짝지은 쌍도 반드시 고려해야 합니다. 음수끼리 곱하면 양수가 되므로, 그 절댓값이 클 경우 오히려 더 큰 결과를 만들어낼 수 있기 때문입니다.
경우 2: k가 홀수인 경우
이 경우는 조금 더 복잡하며, 배열의 최댓값에 따라 세부적으로 나누어 계산해야 합니다.
경우 2.1: 최댓값이 양수인 경우
배열에 양수와 음수가 섞여 있다는 의미입니다. 이때는 가장 큰 k개의 원소를 선택하되, 가능하다면 음수 쪽에서 절댓값이 큰 쌍(두 개씩)을 찾아 결과에 곱해줄 수 있는지 확인합니다.
경우 2.2: 최댓값이 0인 경우
배열 전체가 음수와 0으로만 이루어져 있다는 의미입니다. 홀수 개의 음수를 곱하면 결과가 음수가 되므로, 이 경우 최대 곱은 0이 됩니다.
경우 2.3: 최댓값이 음수인 경우
배열이 오직 음수로만 이루어져 있다는 의미입니다. 이때는 절댓값이 가장 작은 원소들(즉, 정렬 시 가장 큰 값들)을 곱해야 최대 결과를 얻을 수 있습니다.
이처럼 최적의 결과를 얻으려면 배열 원소의 값과 k의 값을 함께 고려해야 합니다.为此, 정렬된 배열의 양쪽 끝(최댓값 쪽과 최솟값 쪽)을 동시에 살펴보면서, 음수 쌍을 곱했을 때 결과가 더 커질 수 있는지 판단하는 방식으로 진행합니다.
해결 방법을 구현한 프로그램
예제 코드
#include <bits/stdc++.h>
using namespace std;
int findMaxSubArrayProduct(int arr[], int n, int k) {
sort(arr, arr + n);
int maxProd = 1;
int i = 0, j = 0;
int maxprod, minprod;
if (arr[n - 1] == 0 && (k % 2 == 1))
return 0;
if (arr[n - 1] <= 0 && (k % 2 == 1)) {
for (i = n - 1; i >= n - k; i--)
maxProd *= arr[i];
return maxProd;
}
i = 0;
j = n - 1;
if (k % 2 == 1) {
maxProd *= arr[j];
j--;
k--;
}
k = k/2;
int it = 0;
while(it < k){
int minprod = arr[i] * arr[i + 1];
int maxprod = arr[j] * arr[j - 1];
if (minprod > maxprod) {
maxProd *= minprod;
i += 2;
} else {
maxProd *= maxprod;
j -= 2;
}
it++;
}
return maxProd;
}
int main() {
int arr[] = { 1, 5, 6, -2, 0, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout<<"The maximum product of subsequence of size "<<k<<" is "<<findMaxSubArrayProduct(arr, n, k);
return 0;
}출력
The maximum product of subsequence of size 3 is 120
위 코드는 배열을 정렬한 후, k가 홀수일 때는 가장 큰 원소 하나를 미리 결과에 포함시키고 남은 횟수만큼 양 끝에서 두 개씩 짝을 지어 비교하며 곱을 누적하는 방식으로 동작합니다. 이를 통해 음수 쌍이 주는 이점까지 놓치지 않고 최대 곱을 구할 수 있습니다.