이 문제에서는 n개의 정수로 이루어진 배열 arr[]과 숫자 d가 주어집니다. 우리의 과제는 특정 차이 조건을 만족하는 쌍(pair)들 중 최대 합을 찾는 프로그램을 C++로 작성하는 것입니다.
문제 설명
배열에서 두 원소의 차이가 d보다 작은 쌍들을 찾아야 하며, 그러한 쌍들의 합이 최대가 되도록 선택해야 합니다.
예제로 문제 이해하기
입력
arr[] = {5, 9, 11, 7, 2, 12, 3}, d = 5출력
47
설명
최대 합에 기여하는 쌍: (3, 5), (7, 9), (11, 12)
합 = 3 + 5 + 7 + 9 + 11 + 12 = 47
해결 접근 방법
가장 단순한 방법은 배열에서 가능한 모든 유효한 쌍을 만들어 각각의 합을 계산하고, 그중 최댓값을 반환하는 것입니다. 하지만 이 방법은 시간 복잡도가 높아 비효율적입니다.
더 효율적인 해결책은 동적 계획법(Dynamic Programming)을 활용하는 것입니다. 최대 합을 구성하는 최적의 쌍을 찾기 위해 먼저 주어진 배열을 오름차순으로 정렬한 후 연산을 진행합니다. 각 원소까지 고려했을 때 얻을 수 있는 쌍의 최대 합을 DP 배열에 저장하며, 현재 원소와 바로 앞 원소가 유효한 쌍(차이가 d 미만)을 이루는지 확인합니다. 쌍을 이룰 수 있다면 해당 쌍의 합을 기존 최대 합과 비교하여 더 큰 값을 저장하고, 그렇지 않다면 기존 최대 합을 그대로 유지합니다.
알고리즘
초기화: DP[n]
1단계 −
배열 arr[]을 오름차순으로 정렬
2단계 −
DP[0] = 0;
3단계 −
i를 1부터 n까지 반복
3.1단계 −
현재 원소와 이전 원소가 쌍을 이룰 수 있는지 확인
조건: arr[i] − arr[i−1] < d
3.2단계 −
쌍을 이룰 수 있다면, 현재 쌍의 합이 기존 최대 합보다 큰지 확인 후 더 큰 값 저장
if ((DP[i−2] + arr[i−1] + arr[i]) > DP[i−1])
DP[i] = DP[i−2] + arr[i−1] + arr[i];
else
DP[i] = DP[i−1];
3.3단계 −
예외 처리: i = 1일 때는 DP[i−2]가 존재하지 않으므로,
첫 번째 쌍의 합만 고려합니다.
4단계 −
DP[n−1] 반환
구현 예제
다음은 위 해결 방법의 동작을 보여주는 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
int CalcmaxPairSum(int arr[], int n, int d) {
sort(arr, arr+n);
int maxSumDP[n];
maxSumDP[0] = 0;
for (int i = 1; i < n; i++) {
maxSumDP[i] = maxSumDP[i−1];
if (arr[i] − arr[i−1] < d) {
if (i >= 2)
if(maxSumDP[i] < (maxSumDP[i−2] + arr[i−1] +
arr[i]))
maxSumDP[i] = (maxSumDP[i−2] + arr[i−1] +
arr[i]);
else
if(maxSumDP[i] < (arr[i−1] + arr[i]))
maxSumDP[i] = arr[i−1] + arr[i];
}
}
return maxSumDP[n−1];
}
int main() {
int arr[] = {5, 9, 11, 7, 2, 12, 3};
int n = 7, d = 5;
cout<<"특정 차이를 가진 쌍의 최대 합은 "<<CalcmaxPairSum(arr, n, d);
return 0;
}출력 결과
특정 차이를 가진 쌍의 최대 합은 47
이 알고리즘은 배열을 정렬하는 데 O(n log n), DP 계산에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 완전 탐색 방식(O(n²))보다 훨씬 효율적으로 문제를 해결할 수 있습니다.