문제 개요
N개의 양의 정수로 이루어진 배열이 주어졌을 때, 배열의 임의의 두 원소 사이에 삽입할 수 있는 가장 작은 양의 정수를 찾는 것이 과제입니다. 이 정수를 삽입한 후, 앞쪽 부분 배열의 합과 뒤쪽 부분 배열의 합이 서로 같아져야 하며, 새로 삽입된 정수는 두 부분 배열 중 어느 쪽에 포함되어도 무방합니다.
예시
배열이 arr = {3, 2, 1, 5, 7, 10}이라면 출력값은 6입니다. 값 6을 5와 7 사이에 삽입하면 왼쪽 부분 배열과 오른쪽 부분 배열의 합이 다음과 같이 같아집니다.
- 왼쪽 합: 3 + 2 + 1 + 5 + 6 = 17
- 오른쪽 합: 7 + 10 = 17
알고리즘
- 배열 전체의 합을 S라고 합니다.
- 인덱스 i까지(해당 인덱스 포함)의 왼쪽 누적 합을 구하고, 이를 L이라고 합니다.
- 그러면 나머지 부분 배열(arr[i+1] .. N)의 합은 S − L이 되며, 이를 R이라고 합니다.
- 두 부분 배열의 합이 같아야 하므로, L과 R 중 더 큰 값을 작은 값에 맞춰 줄여야 합니다. 이때 큰 값과 작은 값의 차이가 바로 필요한 양의 정수의 값입니다.
- 모든 분할 지점(i = 0 ~ n-2)에 대해 위 차이를 계산하고, 그중 최솟값을 반환하면 됩니다.
구현 예제
#include <iostream>
#include <numeric>
#include <climits>
using namespace std;
int getMinimumSplitPoint(int *arr, int n) {
int sum = 0;
sum = accumulate(arr, arr + n, sum);
int leftSum = 0;
int rightSum = 0;
int minValue = INT_MAX;
for (int i = 0; i < n - 1; ++i) {
leftSum += arr[i];
rightSum = sum - leftSum;
if (leftSum > rightSum) {
int e = leftSum - rightSum;
if (e < minValue) {
minValue = e;
}
} else {
int e = rightSum - leftSum;
if (e < minValue) {
minValue = e;
}
}
}
return minValue;
}
int main() {
int arr[] = {3, 2, 1, 5, 7, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int minValue = getMinimumSplitPoint(arr, n);
cout << "Element " << minValue << " needs to be inserted\n";
return 0;
}
코드 설명
accumulate함수를 사용해 배열 전체의 합 S를 한 번에 계산합니다.- 반복문을 돌면서 각 인덱스까지의 왼쪽 누적 합(leftSum)을 갱신하고, 오른쪽 합(rightSum)은 S에서 leftSum을 빼서 구합니다.
- 두 합의 차이(|leftSum − rightSum|)를 계산하여 지금까지의 최솟값(minValue)보다 작으면 갱신합니다.
- 시간 복잡도는 O(N)으로, 배열을 한 번만 순회하면 되므로 매우 효율적입니다.
실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
Element 6 needs to be inserted
즉, 값 6을 삽입하면 배열이 좌우 합이 동일한 두 부분으로 나뉘며, 가능한 삽입 값 중 가장 작은 값임을 확인할 수 있습니다.