C++로 인접하지 않은 두 요소를 선택해 얻을 수 있는 최대 합 구하기

이 문제에서는 배열 arr[]가 주어지며, 인접한 두 요소를 동시에 선택하지 않는 조건 하에서 만들 수 있는 최대 합을 구하는 프로그램을 C++로 작성하는 것이 목표입니다.

문제 설명

배열에서 합을 구할 때, 합에 포함된 숫자들 중 어떤 두 수도 원래 배열에서 서로 인접해서는 안 됩니다. 이 조건을 만족하면서 얻을 수 있는 최대 합을 찾아야 합니다.

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

입력

arr[] = {5, 1, 3, 7, 9, 2, 5}

출력

22

설명

인덱스 0부터 시작해 한 칸씩 건너뛰며 선택한 경우 : 5 + 3 + 9 + 5 = 22
인덱스 1부터 시작해 한 칸씩 건너뛰며 선택한 경우 : 1 + 7 + 2 = 10

해결 접근 방법

이 문제는 대표적인 동적 계획법(DP) 유형으로, 배열의 모든 요소를 한 번씩 순회하면서 두 개의 누적 합을 관리하면 해결할 수 있습니다.

• maxSum1 : 현재 요소를 포함했을 때의 최대 합
• maxSum2 : 현재 요소를 포함하지 않았을 때의 최대 합

매 반복마다 먼저 maxSum2를 max(maxSum1, maxSum2) 값으로 갱신합니다. 즉, 지금까지의 최적해를 저장하는 것입니다. 그다음 maxSum1을 '이전까지의 최적해 + 현재 요소'로 갱신합니다. 이렇게 하면 현재 요소를 선택하더라도 바로 앞 요소와 인접하지 않게 됩니다.

순회가 끝나면 maxSum1과 maxSum2 중 더 큰 값이 곧 정답이 됩니다.

예제 코드

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

#include<iostream>
using namespace std;
int findmaximum(int a, int b){
   if(a > b)
      return a;
      return b;
}
int findMaxSumWOAdjecent(int arr[], int N){
   int maxSum1 = arr[0];
   int maxSum2 = 0;
   int temp;
   for (int i = 1; i < N; i++) {
      temp = findmaximum(maxSum1, maxSum2);
      maxSum1 = maxSum2 + arr[i];
      maxSum2 = temp;
   }
   return (findmaximum(maxSum1, maxSum2));
}
int main(){
   int arr[] = {5, 1, 3, 7, 9, 2, 5};
   int N = sizeof(arr) / sizeof(arr[0]);
   cout<<"인접하지 않은 두 요소를 선택해 얻을 수 있는 최대 합은 "<<findMaxSumWOAdjecent(arr, N);
   return 0;
}

출력 결과

인접하지 않은 두 요소를 선택해 얻을 수 있는 최대 합은 22

정리

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(N), 추가 메모리는 상수 공간만 사용하므로 공간 복잡도는 O(1)입니다. 음수가 포함된 배열의 경우에는 초기값 설정과 갱신 로직을 일부 조정해야 할 수 있으니 참고하시기 바랍니다.