문제 설명
두 개의 정렬된 배열이 주어지며, 두 배열은 일부 공통 원소를 포함할 수 있습니다. 이때 어느 한 배열의 시작 지점에서 두 배열 중 하나의 끝 지점까지 도달하는 최대 합 경로의 총합을 구하는 것이 목표입니다.
중요한 제약 조건은 한 배열에서 다른 배열로 전환할 수 있는 시점이 오직 공통 원소에서만 가능하다는 점입니다. 단, 공통 원소가 반드시 동일한 인덱스 위치에 있어야 하는 것은 아닙니다.
기대되는 시간 복잡도는 O(m+n)이며, 여기서 m은 arr1[]의 원소 개수, n은 arr2[]의 원소 개수입니다.
예제
입력이 다음과 같다면 출력은 35입니다
arr1[] = {2, 3, 7, 10, 12}
arr2[] = {1, 5, 7, 8}
(1 + 5 + 7 + 10 + 12) = 35arr2의 첫 번째 원소인 1에서 시작하여 5로 이동한 뒤, 7에 도달합니다.
7은 공통 원소이므로 이 지점에서 arr1로 전환하고, 이후 10과 12를 순회합니다.
알고리즘
병합 정렬(merge sort)의 병합 과정과 유사한 방식으로 접근합니다. 두 배열에서 공통 지점 사이에 있는 원소들의 합을 각각 계산하고, 공통 지점을 만날 때마다 두 합을 비교하여 더 큰 값을 결과에 더합니다.
result를 0으로 초기화하고, sum1과 sum2 변수도 0으로 초기화합니다. sum1과 sum2는 각각 arr1[]과 arr2[]의 원소 합을 저장하는 용도이며, 이 값들은 두 공통 지점 사이 구간의 합을 나타냅니다.
이제 루프를 돌면서 두 배열의 원소를 동시에 순회하며 현재 원소들을 비교합니다.
arr1[]의 현재 원소가 arr2[]의 현재 원소보다 작으면 sum1을 갱신하고, 반대로 arr2[]의 현재 원소가 더 작으면 sum2를 갱신합니다.
두 배열의 현재 원소가 서로 같다면 sum1과 sum2 중 최댓값을 결과에 더하고, 공통 원소 역시 결과에 추가합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int max(int x, int y){
return (x > y)? x : y;
}
int maxPathSum(int *arr1, int *arr2, int m, int n){
int i = 0, j = 0;
int result = 0, sum1 = 0, sum2 = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
sum1 += arr1[i++];
} else if (arr1[i] > arr2[j]) {
sum2 += arr2[j++];
} else {
result += max(sum1, sum2);
sum1 = 0, sum2 = 0;
while (i < m && j < n && arr1[i] == arr2[j]) {
result = result + arr1[i++];
j++;
}
}
}
while (i < m) {
sum1 += arr1[i++];
}
while (j < n) {
sum2 += arr2[j++];
}
result += max(sum1, sum2);
return result;
}
int main(){
int arr1[] = {2, 3, 7, 10, 12};
int arr2[] = {1, 5, 7, 8};
int m = sizeof(arr1)/sizeof(arr1[0]);
int n = sizeof(arr2)/sizeof(arr2[0]);
cout << "Maximum sum path = " << maxPathSum(arr1, arr2, m, n) << endl;
return 0;
}실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.
Maximum sum path = 35