문제 개요
크기가 n인 배열과 자연수 k가 주어졌을 때, 배열에 대해 총 k번의 "변경 연산"을 수행해야 합니다.
여기서 변경 연산이란 배열의 임의의 원소 arr[i]를 골라 부호를 반대로 바꾸는 것(arr[i] = -arr[i])을 의미합니다. 목표는 k번의 연산을 모두 마친 뒤 배열 원소들의 합이 최대가 되도록 연산 대상을 올바르게 선택하는 것입니다.
입력 예시
arr[] = {7, -3, 5, 4, -1}, k = 2가 입력으로 주어지면 최대 합은 20이 됩니다.
- 1단계: 가장 작은 음수인 -3의 부호를 반전합니다. 배열은 {7, 3, 5, 4, -1}이 됩니다.
- 2단계: 남은 음수 -1의 부호를 반전합니다. 배열은 {7, 3, 5, 4, 1}이 되며, 모든 원소가 양수이므로 합은 20으로 최댓값이 됩니다.
알고리즘 접근 방법
이 문제는 그리디(Greedy) 기법으로 해결할 수 있습니다. 합을 최대화하려면 매 연산마다 현재 배열에서 가장 작은 값을 골라 부호를 반전하는 것이 가장 유리하기 때문입니다.
- 현재 연산 단계에서 배열의 최솟값 원소 arr[i]를 찾아 -arr[i]로 바꿉니다.
- 최솟값이 0이 되었다면 더 이상 변경할 필요가 없습니다(0을 반전해도 합은 변하지 않습니다).
- 이 과정을 k번 반복하면 연산 종료 후 배열의 합이 최대가 됩니다.
k가 남았는데 더 이상 음수가 없는 경우에는 가장 작은 양수를 반복해 반전하는 것이 손실을 최소화하는 방법입니다. 아래 코드처럼 매번 최솟값을 찾아 반전하면 이런 경우도 자연스럽게 처리됩니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n, int k){
for (int i = 1; i <= k; ++i) {
int minValue = INT_MAX;
int index = -1;
for (int j = 0; j < n; ++j) {
if (arr[j] < minValue) {
minValue = arr[j];
index = j;
}
}
if (minValue == 0) {
break;
}
arr[index] = -arr[index];
}
int sum = 0;
for (int i = 0; i < n; ++i) {
sum = sum + arr[i];
}
return sum;
}
int main(){
int arr[] = {7, -3, 5, 4, -1};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout << "최대 합 = " << getMaxSum(arr, n, k) << endl;
return 0;
}
실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
최대 합 = 20
복잡도 분석
시간 복잡도: 한 번의 연산마다 최솟값 탐색에 O(n)이 소요되고, 이를 k번 반복하므로 전체 시간 복잡도는 O(k × n)입니다.
공간 복잡도: 추가적인 메모리를 사용하지 않으므로 O(1)입니다.
참고로 최소 힙(min-heap, priority_queue)을 활용하면 최솟값 탐색을 로그 시간으로 줄여 O((n + k) log n)으로 성능을 개선할 수 있습니다.