이 문제에서는 n개의 요소로 구성된 배열 arr[]가 주어집니다. 배열의 회전만 허용되며, 원하는 만큼 회전을 수행했을 때 Sum(i*arr[i])의 최댓값을 찾아야 합니다.
입력 예시
arr[] = {4, 1, 3, 7, 2}출력
43
설명
배열을 한 번 회전하면 {2, 4, 1, 3, 7}이 되며, 이때 합이 최대가 됩니다.
Sum = 0×2 + 1×4 + 2×1 + 3×3 + 4×7 = 0 + 4 + 2 + 9 + 28 = 43
해결 접근 방법
가장 단순한 방법은 배열을 n번 회전하면서 매번 Sum(i*arr[i])을 직접 계산하고, 그중 최댓값을 반환하는 것입니다. 하지만 이 방법은 시간 복잡도가 O(n²)으로 비효율적입니다.
보다 효율적인 방법은 수학적 공식을 유도하는 것입니다. 회전하지 않은 상태의 합인 sum(0)만 미리 구해 두면, 이후 각 회전의 합을 O(1)에 계산할 수 있어 전체 시간 복잡도를 O(n)까지 줄일 수 있습니다.
공식 유도
k번째 회전 후의 합을 sum(k)라고 하면,
sum(0) = 0*arr[0] + 1*arr[1] + ... + (n-1)*arr[n-1] → 식 1
배열을 한 번 회전하면 합은 다음과 같이 바뀝니다.
sum(1) = 0*arr[n-1] + 1*arr[0] + ... + (n-1)*arr[n-2] → 식 2
식 2에서 식 1을 빼면,
sum(1) - sum(0) = arr[0] + arr[1] + … + arr[n-2] - (n-1)*arr[n-1]
마찬가지로,
sum(2) - sum(1) = arr[0] + arr[1] + … + arr[n-3] - (n-1)*arr[n-2] + arr[n-1]
이를 일반화하면 다음과 같은 점화식을 얻을 수 있습니다.
sum(k) = sum(k-1) + (arr[0] + arr[1] + … + arr[n-1]) - n*arr[n-k]
즉, 배열 전체의 합(arrSum)과 초기 합 sum(0)만 미리 계산해 두면, 반복문 하나로 sum(1)부터 sum(n-1)까지 모든 값을 구할 수 있고, 그중 최댓값이 곧 정답이 됩니다.
구현 예제
#include <iostream>
using namespace std;
int findMaxSumRotation(int arr[], int n){
int arrSum = 0;
int currSum = 0;
// 배열 전체 합과 초기 상태의 sum(0) 계산
for (int i = 0; i < n; i++){
arrSum += arr[i];
currSum += (i * arr[i]);
}
int maxSum = currSum;
// 각 회전마다의 합을 점화식으로 계산
for (int j = 1; j < n; j++){
currSum = currSum + arrSum - n * arr[n-j];
if (currSum > maxSum)
maxSum = currSum;
}
return maxSum;
}
int main(){
int arr[] = {4, 1, 3, 7, 2};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"회전을 사용한 sum(i*arr[i])의 최댓값: "<<findMaxSumRotation(arr, n);
return 0;
}
출력 결과
회전을 사용한 sum(i*arr[i])의 최댓값: 43
복잡도 분석
시간 복잡도: O(n) — 배열을 두 번 순회하므로 선형 시간 안에 해결할 수 있습니다.
공간 복잡도: O(1) — 추가 메모리를 거의 사용하지 않습니다.