이 문제에서는 원형 배열 cirArr[]가 주어집니다. 우리가 작성해야 할 프로그램의 목표는 인접한 두 요소를 동시에 선택하지 않는다는 조건 하에서 원형 배열에서 얻을 수 있는 최대 합을 C++로 구하는 것입니다.
문제 설명
원형 배열에서 요소들의 최대 합을 구해야 하며, 이때 인접한 요소들은 함께 선택될 수 없습니다. 즉, 요소들을 하나씩 건너뛰면서(번갈아 가며) 선택해야 한다는 의미입니다.
원형 배열(Circular Array)은 배열의 마지막 요소가 첫 번째 요소와 연결되어 있는 특수한 형태의 배열입니다.
예제를 통해 문제를 자세히 이해해 보겠습니다.
입력
cirArr[] = {4, 1, 5, 3, 2}출력
9
설명
최대 합을 만들 수 있는 원형 부분 수열은 [4, 5, 2]이며, 이들의 합은 9입니다. 여기서 4와 1, 1과 5처럼 서로 인접한 요소는 동시에 선택할 수 없습니다.
해결 접근 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용하여 해결할 수 있습니다. 핵심 아이디어는 원형 배열을 두 개의 선형 배열로 나누어 생각하는 것입니다.
- 첫 번째 배열: 인덱스 0부터 N-2까지
- 두 번째 배열: 인덱스 1부터 N-1까지
원형 배열에서는 첫 번째 요소와 마지막 요소가 서로 인접해 있기 때문에, 이 두 요소가 동시에 선택되는 경우를 배제하려면 위와 같이 탐색 범위를 나누어야 합니다. 각각의 선형 배열에 대해 인접하지 않은 요소들로 만들 수 있는 최대 합을 구한 뒤, 두 결과값 중 더 큰 값을 반환하면 그것이 곧 정답이 됩니다.
동적 계획법의 상태 정의는 다음과 같습니다. DP[i]는 인덱스 i의 요소를 마지막으로 선택했을 때 얻을 수 있는 최대 합을 저장하며, 점화식은 DP[i] = max(DP[i], DP[j] + cirArr[i]) (단, j는 i-2보다 작은 모든 인덱스)로 표현됩니다.
구현 예제
다음 프로그램은 위에서 설명한 솔루션의 실제 동작을 보여줍니다.
#include <iostream>
using namespace std;
int calcMaxVal(int a, int b){
if(a > b)
return a;
return b;
}
int calcMaxSumSubSeq(int cirArr[], int start, int end, int n) {
int DP[n];
int maxSum = 0;
for (int i = start; i < (end + 1); i++) {
DP[i] = cirArr[i];
if (maxSum < cirArr[i])
maxSum = cirArr[i];
}
for (int i = (start + 2); i < (end + 1); i++) {
for (int j = 0; j < i - 1; j++) {
if (DP[i] < DP[j] + cirArr[i]) {
DP[i] = DP[j] + cirArr[i];
if (maxSum < DP[i])
maxSum = DP[i];
}
}
}
return maxSum;
}
int findMaxSum(int cirArr[], int n){
int maxSumArray1 = calcMaxSumSubSeq(cirArr, 0, (n-2), n);
int maxSumArray2 = calcMaxSumSubSeq(cirArr, 1, (n-1), n);
int maxSum = calcMaxVal(maxSumArray1, maxSumArray2);
return maxSum;
}
int main(){
int cirArr[] = {4, 1, 5, 3, 2};
int n = sizeof(cirArr)/sizeof(cirArr[0]);
cout<<"The maximum sum in circular array such that no two elements are adjacent is "<<findMaxSum(cirArr, n);
return 0;
}출력
The maximum sum in circular array such that no two elements are adjacent is 9
복잡도 분석
- 시간 복잡도: O(N²) — 각 선형 배열에 대해 중첩 반복문을 사용하여 모든 가능한 조합을 검사하기 때문입니다.
- 공간 복잡도: O(N) — 각 인덱스별 최대 합을 저장하기 위한 DP 배열이 필요합니다.
참고로, 이 문제는 각 위치에서 '선택' 또는 '건너뛰기' 두 가지 상태만 추적하는 최적화된 O(N) 방식으로도 해결할 수 있습니다. 다만 위의 구현은 동적 계획법의 기본 원리를 명확하게 보여주므로 학습 목적에 적합합니다.