C++ 배열에서 K칸 간격의 요소를 선택해 얻을 수 있는 최대 합 구하기

문제 개요

이 문제에서는 배열 arr[]와 정수 k가 주어집니다. 우리의 목표는 배열에서 K번째마다 요소를 선택했을 때 만들 수 있는 최대 합을 구하는 것입니다.

문제 설명: 서로 k개의 인덱스만큼 떨어져 있는 요소들을 골라 그 합이 최대가 되도록 해야 합니다. 즉, 다음 식의 값을 최대화하는 것입니다.

sum = arr[i] + arr[i+k] + arr[i + 2*k] + … + arr[i + p*k], 단 (i + p*k) < n

여기서 시작 인덱스 i는 0부터 n-1까지 어떤 위치든 될 수 있으며, 각 시작점에서 k칸씩 건너뛰며 더한 값들 중 가장 큰 것이 정답이 됩니다.

예시를 통해 문제를 자세히 살펴보겠습니다.

입력

arr[] = {5, 3, −1, 2, 4, −5, 6}, k = 4

출력

9

설명

각 시작점에서 k칸(4칸) 간격으로 요소를 더한 결과는 다음과 같습니다.

인덱스 0부터: 5 + 4 = 9
인덱스 1부터: 3 − 5 = −2
인덱스 2부터: −1 + 6 = 5
인덱스 3부터: 2
인덱스 4부터: 4
인덱스 5부터: −5
인덱스 6부터: 6

→ 최댓값은 9

해결 방법 1: 이중 반복문을 이용한 단순 접근

가장 직관적인 방법은 두 개의 중첩 반복문을 사용하는 것입니다. 바깥쪽 반복문은 배열의 각 요소를 시작점으로 순회하고, 안쪽 반복문은 해당 시작점에서 k칸 간격으로 떨어진 모든 요소의 합을 계산합니다.

즉, 각 i에 대해 sum = arr[i] + arr[i+k] + arr[i + 2*k] + … + arr[i + p*k] (단, (i + p*k) < n)을 구하고, 그중 최댓값을 반환하면 됩니다.

이 접근 방식의 동작을 보여주는 프로그램입니다.

예제 코드

#include <iostream>
using namespace std;

int findMaxSumK(int arr[], int n, int K) {
    int maxSum = -1000;
    for (int i = 0; i < n; i++) {
        int currentSum = 0;
        for (int j = i; j < n; j += K) {
            currentSum += arr[j];
        }
        maxSum = max(maxSum, currentSum);
    }
    return maxSum;
}

int main() {
    int arr[] = {5, 3, -1, 2, 4, -5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
    cout << "배열에서 K번째 요소를 선택해 얻는 최대 합: "
         << findMaxSumK(arr, n, K);
    return 0;
}

출력

배열에서 K번째 요소를 선택해 얻는 최대 합: 13

K = 3일 경우, 인덱스 0에서 시작하면 5 + 2 + 6 = 13이 되어 최대 합이 됩니다.

이 방법의 시간 복잡도는 O(n²)로, 배열의 크기가 커지면 비효율적일 수 있습니다.

해결 방법 2: 접미사 합(Suffix Sum)을 이용한 효율적 접근

더 효율적인 방법은 접미사 합 개념을 활용하는 것입니다. 배열을 뒤에서부터 순회하면서, 각 인덱스 i에서 시작해 k칸 간격으로 더한 합을 미리 저장하는 것입니다.

점화식은 다음과 같습니다.

• suffSum[i] = suffSum[i + K] + arr[i] — i + K < n인 경우
• suffSum[i] = arr[i] — 그 외의 경우 (배열 끝에 도달)

모든 suffSum[i] 값 중 최댓값이 곧 정답이 되며, 이 방식은 시간 복잡도 O(n), 공간 복잡도 O(n)으로 훨씬 빠르게 동작합니다.

이 접근 방식의 동작을 보여주는 프로그램입니다.

예제 코드

#include <iostream>
using namespace std;

int findMaxSumK(int arr[], int n, int K) {
    int maxSum = -1000;
    int suffSum[n];

    for (int i = n - 1; i >= 0; i--) {
        if (i + K < n)
            suffSum[i] = suffSum[i + K] + arr[i];
        else
            suffSum[i] = arr[i];
        maxSum = max(maxSum, suffSum[i]);
    }
    return maxSum;
}

int main() {
    int arr[] = {5, 3, -1, 2, 4, -5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
    cout << "배열에서 K번째 요소를 선택해 얻는 최대 합: "
         << findMaxSumK(arr, n, K);
    return 0;
}

출력

배열에서 K번째 요소를 선택해 얻는 최대 합: 13

마무리

배열에서 K칸 간격의 요소 합의 최댓값을 구하는 문제는 단순한 이중 반복문으로도 해결할 수 있지만, 접미사 합을 활용하면 한 번의 역방향 순회만으로 O(n) 시간에 효율적으로 해결할 수 있습니다. 입력 배열의 크기가 클수록 후자의 접근 방식이 실질적인 성능 이점을 제공합니다.