문제 설명
(2 × n − 1)개의 정수로 이루어진 배열이 주어집니다. 우리는 이 배열에서 정확히 n개의 요소를 선택하여 각각의 부호를 변경(-1을 곱하기)할 수 있습니다. 이때 얻을 수 있는 배열 합의 최댓값을 구하는 것이 목표입니다.
예시
입력 배열이 {-2, 100, -3}이라고 가정해 보겠습니다. 이 경우 -2와 -3의 부호를 변경하면 최대 합을 얻을 수 있습니다.
부호 변경 후 배열은 {2, 100, 3}이 되며, 이 배열의 최대 합은 105입니다.
해결 알고리즘
- 배열 내 음수의 개수를 셉니다.
- 모든 요소의 절댓값을 더하여 전체 합을 계산합니다.
- 요소들의 절댓값 중 최솟값(m)을 찾습니다.
- 음수 개수가 홀수이면서 n이 짝수라면, 합에서 2×m을 뺀 값이 최대 합이 됩니다. 그렇지 않다면 현재 합이 곧 최대 합입니다.
알고리즘의 핵심 아이디어
음수를 모두 양수로 바꾸는 것이 항상 유리하지만, 음수의 개수가 홀수이고 n이 짝수인 경우 하나의 음수가 반드시 남게 됩니다. 이때 손실을 최소화하기 위해 절댓값이 가장 작은 요소(m)를 음수로 두는 것이 최선이며, 따라서 전체 합에서 2×m을 빼주면 됩니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n) {
int negtiveCnt = 0;
int sum = 0;
int m = INT_MAX;
for (int i = 0; i < 2 * n - 1; ++i) {
if (arr[i] < 0) {
++negtiveCnt;
}
sum = sum + abs(arr[i]);
m = min(m, abs(arr[i]));
}
if (negtiveCnt % 2 && n % 2 == 0) {
sum = sum - 2 * m;
return sum;
}
return sum;
}
int main() {
int arr[] = {-2, 100, -3};
int n = 2;
cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
return 0;
}
실행 결과
Maximum sum = 105
정리
이 문제는 시간 복잡도 O(2n−1), 즉 O(n)에 해결할 수 있습니다. 절댓값의 합을 기본으로 하되, 음수 개수와 n의 홀짝성에 따라 최소 절댓값만큼의 손실이 발생하는지 판단하는 것이 핵심 포인트입니다.