문제 개요
주어진 배열 arr[]에서 특정 인덱스 i를 기준으로 접두사 합(prefix sum)과 접미사 합(suffix sum)이 서로 같아지는 지점을 찾고, 그중 최댓값을 구하는 문제입니다.
여기서 접두사 합은 배열의 시작부터 인덱스 i까지의 원소 합을 의미하고, 접미사 합은 인덱스 i부터 배열의 끝까지의 원소 합을 의미합니다. 이렇게 두 값이 일치하는 지점을 '평형 지점(equilibrium point)'이라고 부르며, 해당 지점에서의 합계가 바로 평형 합계입니다.
예시
입력 배열이 다음과 같다고 가정해 보겠습니다.
Arr[] = {1, 2, 3, 5, 3, 2, 1}이 경우 출력값은 11입니다. 그 이유는 다음과 같습니다.
- 접두사 합 = arr[0..3] = 1 + 2 + 3 + 5 = 11
- 접미사 합 = arr[3..6] = 5 + 3 + 2 + 1 = 11
인덱스 3(값 5)을 기준으로 접두사 합과 접미사 합이 모두 11로 일치하며, 이것이 가능한 평형 합계 중 가장 큰 값입니다.
알고리즘
이 문제는 각 인덱스별로 접두사 합과 접미사 합을 미리 계산해 둔 뒤 비교하는 방식으로 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- 배열을 순차적으로 탐색하면서 각 인덱스까지의 접두사 합을 presum[] 배열에 저장합니다. 이때 presum[i]는 부분 배열 arr[0..i]의 합을 나타냅니다.
- 배열을 역방향으로 다시 탐색하면서 각 인덱스부터 끝까지의 접미사 합을 suffsum[] 배열에 저장합니다. 이때 suffsum[i]는 부분 배열 arr[i..n-1]의 합을 나타냅니다.
- 모든 인덱스에 대해 presum[i]와 suffsum[i]가 같은지 확인하고, 같다면 현재까지의 최댓값과 비교하여 더 큰 값을 결과로 갱신합니다.
이 방법은 시간 복잡도 O(n), 공간 복잡도 O(n)으로 동작하며, 모든 인덱스를 한 번씩만 확인하면 되므로 효율적입니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n) {
int preSum[n];
int suffSum[n];
int result = INT_MIN;
preSum[0] = arr[0];
for (int i = 1; i < n; ++i) {
preSum[i] = preSum[i - 1] + arr[i];
}
suffSum[n - 1] = arr[n - 1];
if (preSum[n - 1] == suffSum[n - 1]) {
result = max(result, preSum[n - 1]);
}
for (int i = n - 2; i >= 0; --i) {
suffSum[i] = suffSum[i + 1] + arr[i];
if (suffSum[i] == preSum[i]) {
result = max(result, preSum[i]);
}
}
return result;
}
int main() {
int arr[] = {1, 2, 3, 5, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Max equlibrium sum = " << getMaxSum(arr, n) << endl;
return 0;
}코드 설명
- getMaxSum 함수: 먼저 정방향 반복문으로 preSum 배열을 채우고, 이후 역방향 반복문으로 suffSum 배열을 채우면서 동시에 두 값이 일치하는지 검사합니다.
- result 초기화: INT_MIN으로 초기화하여 어떤 유효한 평형 합계보다 작게 설정함으로써, 평형 지점이 하나라도 존재하면 올바른 값이 반환되도록 합니다.
- main 함수: 예시 배열을 선언하고 sizeof 연산자로 배열 크기를 계산한 후 getMaxSum 함수를 호출해 결과를 출력합니다.
실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.
Max equlibrium sum = 11
결과값 11은 앞서 살펴본 것처럼 인덱스 3을 기준으로 한 접두사 합과 접미사 합이 일치하는 가장 큰 평형 합계입니다.