문제 개요
양수와 음수로 이루어진 정수 배열과 숫자 K가 주어집니다. 목표는 배열의 원소를 정확히 K번 변경한 후 얻을 수 있는 최대 합을 구하는 것입니다. 여기서 한 번의 변경 연산은 특정 원소에 -1을 곱해 부호를 뒤집는 것을 의미합니다.
접근 방법
핵심 아이디어는 가능한 한 많은 음수를 양수로 바꾸는 것입니다. 음수의 개수를 N이라 할 때, 먼저 배열을 오름차순으로 정렬한 뒤 다음 규칙을 따릅니다.
- N < K인 경우: N번의 연산으로 모든 음수가 양수가 되고, K−N번의 연산이 남습니다.
- K−N이 짝수인 경우: 같은 원소의 부호를 짝수 번 바꾸면 원래 값으로 돌아오므로, 남은 연산은 결과에 영향을 주지 않습니다. 아무것도 하지 않으면 됩니다.
- K−N이 홀수인 경우: 남은 연산 중 한 번은 어쩔 수 없이 부호를 바꿔야 하므로, 배열에서 가장 작은 값의 부호를 한 번 뒤집습니다. 이렇게 하면 손실이 최소화되어 전체 합이 최대가 됩니다.
- N > K인 경우: 절댓값이 큰 음수부터 차례로 K개의 음수만 양수로 바꾸면 합이 최대가 됩니다.
입력 예시 1
Arr[]= { 0,-2,6,4,8,2,-3 } K=4출력
Maximum array sum is : 25
설명 − 네 번의 변경 과정은 다음과 같습니다.
1. 0,2,6,4,8,2,-3 → -2를 2로 변경 2. 0,2,6,4,8,2,3 → -3을 3으로 변경 3. 0,-2,6,4,8,2,3 → 2를 -2로 변경 4. 0,2,6,4,8,2,3 → -2를 다시 2로 변경 최대 합은 25
입력 예시 2
Arr[]= { -1,-2,-3,-4,-5,-6,-7 } K=4출력
Maximum array sum is : 16
설명 − 네 번의 변경 과정은 다음과 같습니다.
1. -1,-2,-3,-4,-5,-6,7 → -7을 7로 변경 2. -1,-2,-3,-4,-5,6,7 → -6을 6으로 변경 3. -1,-2,-3,-4,5,6,7 → -5를 5로 변경 4. -1,-2,-3,4,5,6,7 → -4를 4로 변경 최대 합은 16
프로그램에서 사용된 접근 방식
- 정수 배열 Arr[]에 정수들을 저장합니다.
- 정수 'size'에는 배열의 길이가 저장되고, K가 초기화됩니다.
- 함수 returnSum(int arr[], int n, int k)은 배열, 배열의 크기, k를 입력받아 정확히 k번의 연산 후 얻을 수 있는 원소들의 최대 합을 반환합니다.
- 먼저 sort(arr, arr+n)을 사용해 배열을 오름차순으로 정렬합니다.
- 마지막 인덱스에 도달하거나 k가 0이 될 때까지, 모든 음수 원소에 arr[i]*-1 연산을 적용합니다.
- k가 음수 원소의 개수보다 작다면, 위 단계에서 k개의 음수만 양수로 바뀝니다.
- k가 더 크다면 남은 k값이 홀수인지 짝수인지 확인합니다.
- 남은 k가 홀수라면 최솟값 원소의 부호를 한 번 뒤집습니다. (-1을 홀수 번 곱하는 것은 한 번 곱하는 것과 동일합니다.)
- 남은 k가 짝수라면 부호 변경은 효과가 없으므로 아무것도 하지 않습니다.
- 배열 전체의 합을 계산해 결과를 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int returnSum(int arr[], int n, int k){
// 배열 원소를 오름차순으로 정렬
sort(arr, arr + n);
// 가장 작은 값부터 시작해
// 음수 원소들의 부호를 변경
// k번 반복할 때마다 하나의 음수가 양수로 변환됨
for (int i = 0; i < n; i++) {
if (k > 0 && arr[i] < 0) {
arr[i] = arr[i] * -1;
k--;
}
}
// k가 0이 아니면서 홀수라면
// 최솟값 원소의 부호를 한 번 변경
if (k % 2 == 1) {
int minVal = arr[0];
int pos = 0; // 최솟값의 인덱스
for (int i = 1; i < n; i++) {
if (arr[i] < minVal) {
minVal = arr[i];
pos = i;
}
}
arr[pos] *= -1;
}
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
int main(){
int Arr[] = { -3, 4, -3, 6, 8 };
int size = 5;
int K = 4;
cout << "Maximum array sum that can be obtained after exactly k changes : "
<< returnSum(Arr, size, K) << endl;
return 0;
}출력
Maximum array sum that can be obtained after exactly k changes : 24
복잡도 분석
시간 복잡도: O(n log n) — 배열 정렬이 지배적인 비용입니다.
공간 복잡도: O(1) — 추가 메모리 없이 입력 배열 자체를 수정하여 사용합니다.