Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 세 배열의 최대 합 구하기: 같은 배열을 연속으로 선택할 수 없는 경우

이 문제에서는 크기가 N인 세 개의 배열 arr1[], arr2[], arr3[]가 주어집니다. 우리의 과제는 같은 배열에서 요소를 연속적으로 선택하는 것이 허용되지 않는다는 조건 아래에서 세 배열로부터 얻을 수 있는 최대 합을 구하는 프로그램을 C++로 작성하는 것입니다.

문제 설명

각 인덱스 i마다 하나의 요소를 선택하여 총 N개의 요소를 고르고, 그 합이 최대가 되도록 만들어야 합니다. 즉, i번째 선택 값은 arr1[i], arr2[i], arr3[i] 중 하나여야 합니다. 단, 연속된 두 요소를 같은 배열에서 선택할 수 없다는 제약 조건이 반드시 지켜져야 합니다.

예시를 통해 문제를 이해해 보겠습니다.

입력

arr1[] = {5, 8, 9, 20},
arr2[] = {7, 12, 1, 10},
arr3[] = {8, 9, 10, 11}
N = 4

출력

50

설명

i = 1일 때 arr3에서 8을 선택하고, i = 2일 때 arr2에서 12를, i = 3일 때 arr3에서 10을, 마지막으로 i = 4일 때 arr1에서 20을 선택합니다. 따라서 합계는 8 + 12 + 10 + 20 = 50이 되며, 이 선택 과정에서 인접한 두 요소가 같은 배열에서 선택된 적이 없으므로 제약 조건을 만족합니다.

해결 접근 방법

이 문제는 동적 계획법(Dynamic Programming)과 메모이제이션(Memoization)을 활용하면 효율적으로 해결할 수 있습니다. 이미 계산한 값을 저장해 두면 불필요한 중복 계산을 피할 수 있습니다.

먼저 2차원 배열 DP[][]를 생성합니다. 여기서 DP[i][j]는 i번째 인덱스까지 고려했을 때 j번째 배열에서 요소를 선택한 경우의 최대 합을 의미합니다. 현재 위치에서 가능한 값을 구한 뒤, 직전에 선택하지 않은 나머지 두 배열에서 다음 요소를 선택하도록 재귀적으로 호출하는 방식으로 진행합니다.

알고리즘 단계

  1. DP 테이블의 모든 값을 -1로 초기화합니다(아직 계산되지 않은 상태).
  2. 현재 인덱스와 직전에 선택한 배열의 번호를 매개변수로 받는 재귀 함수를 정의합니다.
  3. 직전 배열과 다른 두 배열에서 요소를 선택하는 두 가지 경우를 각각 계산하여 더 큰 값을 저장합니다.
  4. main 함수에서 세 배열 각각을 시작점으로 삼는 경우를 모두 계산한 뒤, 그중 최댓값을 출력합니다.

C++ 코드 예시

아래 프로그램은 위에서 설명한 솔루션의 동작을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
const int N = 3;
int findMaxVal(int a, int b){
    if(a > b)
        return a;
    return b;
}
int FindMaximumSum(int index, int arrNo, int arr1[], int arr2[], int arr3[], int n, int DP[][N]){
    if (index == n)
        return 0;
    if (DP[index][arrNo] != -1)
        return DP[index][arrNo];
    int maxVal = -1;
    if (arrNo == 0){
        maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));
        maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));
    }
    else if (arrNo == 1){
        maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));
        maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));
    }
    else if (arrNo == 2){
        maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));
        maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));
    }
    return DP[index][arrNo] = maxVal;
}
int main(){
    int arr1[] = { 5, 8, 9, 20 };
    int arr2[] = { 7, 12, 1, 10 };
    int arr3[] = { 8, 9, 10, 11 };
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int DP[n][N];
    memset(DP, -1, sizeof DP);
    int val1 = FindMaximumSum(0, 0, arr1, arr2, arr3, n, DP);
    int val2 = FindMaximumSum(0, 1, arr1, arr2, arr3, n, DP);
    int val3 = FindMaximumSum(0, 2, arr1, arr2, arr3, n, DP);
    cout<<"같은 배열에서 연속으로 요소를 선택하지 않는 조건의 세 배열 최대 합은 "<<findMaxVal(val1, findMaxVal(val2, val3));
    return 0;
}

출력 결과

같은 배열에서 연속으로 요소를 선택하지 않는 조건의 세 배열 최대 합은 50

복잡도 분석

  • 시간 복잡도: O(N) — 메모이제이션 덕분에 각 상태(인덱스 × 배열 번호)는 한 번만 계산되므로 전체 상태 수는 3N입니다.
  • 공간 복잡도: O(N) — DP 테이블 저장과 재귀 호출 스택에 추가 공간이 필요합니다.