이 글에서는 주어진 n개의 숫자로 이루어진 배열을 재정렬하는 문제를 다룹니다. 기본적으로 배열에서 요소를 선택해야 하며, 각 요소를 선택할 때마다 현재 요소의 값 × 이전에 선택한 요소의 개수만큼 점수를 얻게 됩니다. 목표는 이 점수를 최대화하도록 요소를 선택하는 것입니다.
문제 예시
입력 : arr[] = { 3, 1, 5, 6, 3 }
배열에 주어진 순서 그대로 요소를 선택하면 획득 점수는 다음과 같습니다.
= 3 * 0 + 1 * 1 + 5 * 2 + 6 * 3 + 3 * 4
= 41
점수를 최대화하려면 { 1, 3, 3, 5, 6 } 순서로 요소를 선택해야 합니다.
= 1 * 0 + 3 * 1 + 3 * 2 + 5 * 3 + 6 * 4
= 48 (최댓값)
출력 : 48
입력 : arr[] = { 2, 4, 7, 1, 8 }
출력 : 63해결 방법
예시를 살펴보면 알 수 있듯이, 점수를 최대화하려면 요소를 작은 값부터 큰 값 순서로 선택해야 합니다. 그 이유는 간단합니다. 인덱스가 커질수록 곱해지는 계수(i)가 커지기 때문에, 큰 값을 뒤쪽 인덱스에 배치하는 것이 유리합니다. 문제 해결 접근 방식은 다음과 같습니다.
- 주어진 배열을 오름차순으로 정렬합니다.
- 인덱스 0부터 끝까지 순서대로 요소를 선택합니다.
- 각 요소를 선택할 때 얻는 점수(현재 요소 × 현재 인덱스)를 계산하여 누적합니다.
C++ 구현 코드
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main () {
int arr[] = { 2, 4, 7, 1, 8 };
int n = sizeof (arr) / sizeof (arr[0]);
// 배열을 오름차순으로 정렬
sort (arr, arr + n);
int points = 0;
// 배열을 순회하면서 점수 계산
for (int i = 0; i < n; i++) {
points += arr[i] * i;
}
cout << "Maximum points: " << points;
return 0;
}실행 결과
Maximum points: 63
코드 설명
위 C++ 코드는 이해하기 매우 쉽습니다. 먼저 sort() 함수를 사용해 배열을 오름차순으로 정렬한 후, for 반복문으로 배열을 처음부터 끝까지 순회하며 각 요소를 선택했을 때 얻는 점수(arr[i] * i)를 계산하고 누적합니다. 시간 복잡도는 정렬에 의해 지배되므로 O(n log n)입니다.
마무리
이 글에서는 i * arr[i]로 점수가 계산되는 상황에서 점수를 최대화하기 위해 배열의 요소를 선택·재정렬하는 문제를 살펴보았습니다. 탐욕(Greedy) 알고리즘을 적용해 배열을 오름차순으로 정렬한 뒤 순서대로 더하는 방식으로 최댓값을 구할 수 있으며, 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 도움이 되었기를 바랍니다.