이 문제에서는 N개의 정수로 이루어진 배열 arr[]과 두 개의 인덱스 값 x, y가 주어집니다. 목표는 인덱스 x까지의 접두사(prefix)로 만들 수 있는 최대 합 증가 부분 수열을 구하되, 그 뒤에 위치한 인덱스 y의 요소를 반드시 포함해야 한다는 조건을 만족하는 프로그램을 C++로 작성하는 것입니다.
문제 설명
인덱스 x까지의 범위에서 증가 부분 수열의 최대 합을 구하고, 마지막에 인덱스 y에 해당하는 요소를 반드시 더해야 합니다.
예제를 통해 문제를 자세히 살펴보겠습니다.
입력
arr[] = {1, 5, 9, 131, 6, 100, 11, 215}, x = 4, y = 6
출력
26
설명
인덱스 x(4) 이전까지의 요소들로 증가 부분 수열 {1, 5, 9}를 만들고, 마지막에 arr[6] = 11을 추가합니다.
따라서 최종 부분 수열은 {1, 5, 9, 11}이 되며, 합은 1 + 5 + 9 + 11 = 26입니다.
해결 접근 방식
가장 단순한 방법은 인덱스 x까지의 새로운 배열을 만들고 그 끝에 인덱스 y의 요소를 붙인 뒤, 가능한 모든 증가 부분 수열을 계산하는 것입니다. 이때 arr[y]를 포함할 수 없는 수열은 제외하고, 남은 수열 중 최대합(maxSum)을 찾으면 됩니다.
보다 효과적인 방법은 동적 계획법(Dynamic Programming)을 활용하는 것입니다. 2차원 배열 DP[][]를 만들어 각 상태별 증가 부분 수열의 최대 합을 저장하면, DP[x][y] 값이 '인덱스 x까지의 최대 합에 arr[y]를 포함한 값'을 나타내도록 할 수 있습니다.
예제
아래 프로그램은 위에서 설명한 솔루션의 동작을 보여줍니다.
#include <iostream>
using namespace std;
int DP[100][100];
void preCalcMaxSum(int arr[], int N){
for (int i = 0; i < N; i++) {
if (arr[i] > arr[0])
DP[0][i] = arr[i] + arr[0];
else
DP[0][i] = arr[i];
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[j] > arr[i] && j > i) {
if (DP[i - 1][i] + arr[j] > DP[i - 1][j])
DP[i][j] = DP[i - 1][i] + arr[j];
else
DP[i][j] = DP[i - 1][j];
}
else
DP[i][j] = DP[i - 1][j];
}
}
}
int main() {
int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
int N = sizeof(arr) / sizeof(arr[0]);
int x = 4, y = 6;
preCalcMaxSum(arr, N);
cout<<"접두사와 그 뒤의 지정된 요소를 반드시 포함하는 최대 합 증가 부분 수열의 합은 ";
cout<<DP[x][y];
return 0;
}
출력
접두사와 그 뒤의 지정된 요소를 반드시 포함하는 최대 합 증가 부분 수열의 합은 26
더 효율적인 접근 방식은 인덱스 x까지의 증가 부분 수열을 구하되, 수열의 가장 큰 요소가 인덱스 y의 요소보다 작은 경우만 고려하는 것입니다. 이렇게 하면 인덱스 y의 요소를 항상 뒤에 붙일 수 있으며, 이 역시 동적 계획법으로 해결할 수 있습니다.
예제
아래 프로그램은 이 방식의 동작을 보여줍니다.
#include <iostream>
using namespace std;
int calcMaxSum(int arr[], int n, int x, int y){
int DP[x] = {0};
int maxSum = -1;
for (int i = 0; i <= x; i++)
DP[i] = arr[i];
for (int i = 0; i <= x; i++) {
if (arr[i] >= arr[y]) {
continue;
}
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j])
DP[i] += arr[j];
maxSum = max(maxSum, DP[i]);
}
}
if (maxSum == -1) {
return arr[y];
}
return maxSum + arr[y];
}
int main(){
int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
int N = sizeof(arr) / sizeof(arr[0]);
int x = 4, y = 6;
cout<<"접두사와 그 뒤의 지정된 요소를 반드시 포함하는 최대 합 증가 부분 수열의 합은 ";
cout<<calcMaxSum(arr, N, x, y);
return 0;
}
출력
접두사와 그 뒤의 지정된 요소를 반드시 포함하는 최대 합 증가 부분 수열의 합은 26