문제 설명
N개의 정수로 이루어진 배열이 주어졌을 때, 배열의 요소들을 자유롭게 재배열할 수 있다면 Σarr[i]×i(단, i = 0, 1, 2, ..., n-1)의 최대값을 구하는 것이 이번 문제의 목표입니다.
예를 들어 입력 배열이 {4, 1, 6, 2}라고 가정해 보겠습니다. 요소들을 오름차순으로 정렬하면 최대 합은 28이 됩니다.
{1, 2, 4, 6} = (1 × 0) + (2 × 1) + (4 × 2) + (6 × 3) = 28접근 방법: 재배열 부등식
이 문제의 핵심 아이디어는 재배열 부등식(Rearrangement Inequality)에 있습니다. 두 수열을 같은 방향(오름차순)으로 정렬한 뒤 대응되는 원소끼리 곱하여 합산하면 그 값이 최대가 된다는 원리입니다.
즉, 값이 클수록 더 큰 인덱스와 곱해지는 것이 유리하므로, 배열을 오름차순으로 정렬하면 가장 작은 값은 인덱스 0과, 가장 큰 값은 인덱스 n-1과 곱해져 전체 합이 자연스럽게 최대화됩니다.
알고리즘
1. 배열을 오름차순으로 정렬한다.
2. 배열을 순회하며 각 요소에 해당 인덱스 i(0, 1, 2, ..., n-1)를 곱한다.
3. 누적된 합계를 반환한다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n){
sort(arr, arr + n);
int sum = 0;
for (int i = 0; i < n; ++i) {
sum = sum + arr[i] * i;
}
return sum;
}
int main(){
int arr[] = {4, 1, 6, 2};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
return 0;
}
실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
Maximum sum = 28
시간 복잡도 분석
- 정렬 단계: O(n log n)
- 합계 계산 단계: O(n)
전체 시간 복잡도는 정렬이 지배하므로 O(n log n)입니다. 공간 복잡도는 추가 메모리 없이 제자리(in-place) 정렬을 사용하므로 O(1)입니다.
마무리
이 문제는 정렬이라는 기본 연산만으로 해결할 수 있는 대표적인 그리디(Greedy) 유형 문제입니다. 음수가 포함된 배열이나 내림차순 정렬이 필요한 변형 문제(최솟값 구하기 등)에도 동일한 재배열 부등식 개념을 적용할 수 있으니 함께 익혀두면 좋습니다.