C++로 배열의 모든 회전 중 i*arr[i] 합의 최댓값 구하기

문제 개요

이 문제에서는 배열 arr가 주어지며, 주어진 배열의 모든 회전(rotation) 중에서 i × arr[i]의 합이 최대가 되는 값을 찾는 프로그램을 C++로 작성하는 것이 목표입니다.

문제 설명 − 배열을 회전할 때마다 각 원소에 해당 인덱스를 곱한 값({i * arr[i]})의 합을 계산하고, 그 합들 중 최댓값을 구합니다.

예제를 통해 문제를 이해해 보겠습니다.

입력 − arr = {4, 8, 1, 5}

출력 − 37

설명 −

모든 회전과 i*arr[i]의 합 :
{4, 8, 1, 5} = 4*0 + 8*1 + 1*2 + 5*3 = 25
{8, 1, 5, 4} = 8*0 + 1*1 + 5*2 + 4*3 = 23
{1, 5, 4, 8} = 1*0 + 5*1 + 4*2 + 8*3 = 37
{5, 4, 8, 1} = 5*0 + 4*1 + 8*2 + 1*3 = 23
세 번째 회전에서 최댓값 37을 얻습니다.

방법 1: 브루트 포스 접근 (O(n²))

가장 단순한 해결 방법은 각 회전마다 모든 원소에 인덱스를 곱한 값의 합을 직접 계산한 뒤, 그중 최댓값을 찾는 것입니다. 이를 위해 배열을 n번 회전하면서 매번 합을 계산하고, 현재 회전의 합이 이전에 저장된 maxSum보다 크면 값을 갱신합니다.

구현 예제

#include<iostream>
using namespace std;

int findMax(int a, int b){
    if(a > b)
        return a;
    return b;
}

int calculateMaxSum(int arr[], int n){
    int maxSum = 0, sum = 0;
    for (int i = 0; i < n; i++){
        sum = 0;
        for (int j = 0; j < n; j++){
            int index = (i + j) % n;
            sum += j * arr[index];
        }
        maxSum = findMax(maxSum, sum);
    }
    return maxSum;
}

int main(){
    int arr[] = {4, 8, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "배열의 모든 회전 중 i*arr[i]의 최대 합은 " << calculateMaxSum(arr, n);
    return 0;
}

출력

배열의 모든 회전 중 i*arr[i]의 최대 합은 37

방법 2: 효율적인 접근 (O(n))

더 효율적인 방법은 이전 회전의 합을 활용하여 다음 회전의 합을 계산하는 것입니다. 다음 공식을 사용합니다.

nextSum = currentSum - (arraySum - arr[i-1]) + arr[i-1] * (n-1)

공식의 원리 − 배열을 한 칸 회전하면 나머지 원소들의 인덱스는 1씩 줄어들므로, 현재 합에서 배열 전체의 합(arraySum)을 빼줍니다. 단, 맨 앞으로 이동하는 원소 arr[i-1]은 새로운 인덱스 n-1을 갖게 되므로, arr[i-1] * (n-1)을 다시 더해줍니다.

이 공식으로 nextSum을 구한 뒤, 루프 내에서 nextSum이 maxSum보다 크면 maxSum을 nextSum으로 갱신합니다.

구현 예제

#include<iostream>
using namespace std;

int findMax(int a, int b){
    if(a > b)
        return a;
    return b;
}

int calculateMaxSum(int arr[], int n){
    int arraySum = 0, currentSum = 0, nextSum;
    for (int i = 0; i < n; i++){
        arraySum += arr[i];
        currentSum += i * arr[i];
    }
    int maxSum = currentSum;
    for (int i = 1; i < n; i++){
        nextSum = currentSum - (arraySum - arr[i-1]) + arr[i-1] * (n - 1);
        currentSum = nextSum;
        maxSum = findMax(maxSum, nextSum);
    }
    return maxSum;
}

int main(){
    int arr[] = {4, 8, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "배열의 모든 회전 중 i*arr[i]의 최대 합은 " << calculateMaxSum(arr, n);
    return 0;
}

출력

배열의 모든 회전 중 i*arr[i]의 최대 합은 37

복잡도 분석

방법 1(브루트 포스): 시간 복잡도 O(n²), 공간 복잡도 O(1)

방법 2(효율적 접근): 시간 복잡도 O(n), 공간 복잡도 O(1)