C++로 차이가 K 미만인 쌍의 최대 합 구하기

이 글에서는 C++를 활용해 특정 차이 조건을 만족하는 쌍(pair)의 최대 합을 구하는 프로그램을 작성하는 방법을 알아보겠습니다.

문제 정의

정수로 이루어진 배열 하나와 값 K가 주어집니다. 이때 두 원소의 차이가 K 미만일 때만 해당 원소들을 하나의 쌍으로 묶을 수 있으며, 서로 겹치지 않는(disjoint) 쌍들을 구성해 그 원소들의 합이 최대가 되도록 만들어야 합니다.

예를 들어 배열이 {3, 5, 10, 15, 17, 12, 9}이고 K가 4라고 가정해 보겠습니다. 이 경우 최적의 쌍은 (3, 5), (10, 12), (15, 17)이며, 정답은 8 + 22 + 32 = 62가 됩니다.

접근 방법: 동적 계획법(DP)

먼저 배열을 오름차순으로 정렬합니다. 정렬된 상태에서는 인접한 원소끼리만 쌍이 될 수 있으므로, 동적 계획법으로 문제를 효율적으로 해결할 수 있습니다.

dp[i]를 "첫 번째 원소부터 i번째 원소까지 고려했을 때 얻을 수 있는 최대 합"이라고 정의합니다. 각 위치에서 선택할 수 있는 경우의 수는 두 가지입니다.

i번째 원소를 쌍에 포함하지 않는 경우: dp[i] = dp[i-1]
i번째 원소와 i-1번째 원소를 쌍으로 묶는 경우(두 원소의 차이가 K 미만일 때만 가능): dp[i] = dp[i-2] + arr[i] + arr[i-1]

두 값 중 더 큰 값을 dp[i]에 저장하고, 최종적으로 dp[N-1]을 반환하면 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 겹치지 않는 쌍들의 최대 합을 반환하는 함수
int maxSumPairWithDifferenceLessThanK(int arr[], int N, int K){
    sort(arr, arr+N);
    int dp[N];
    dp[0] = 0;
    for (int i = 1; i < N; i++) {
        // 기본값: 현재 원소를 쌍에 포함하지 않음
        dp[i] = dp[i-1];
        // 차이가 K 미만이라면 현재 원소와 이전 원소를 묶어보고 더 큰 값 선택
        if (arr[i] - arr[i-1] < K) {
            if (i >= 2)
                dp[i] = max(dp[i], dp[i-2] + arr[i] + arr[i-1]);
            else
                dp[i] = max(dp[i], arr[i] + arr[i-1]);
        }
    }
    return dp[N - 1];
}

int main() {
    int arr[] = {3, 5, 10, 15, 17, 12, 9};
    int N = sizeof(arr)/sizeof(int);
    int K = 4;
    cout << maxSumPairWithDifferenceLessThanK(arr, N, K);
    return 0;
}

실행 결과

복잡도 분석

시간 복잡도: 정렬에 O(N log N), DP 계산에 O(N)이 소요되므로 전체 시간 복잡도는 O(N log N)입니다.

공간 복잡도: DP 배열을 저장하기 위해 O(N)의 추가 공간이 필요합니다.