C++ 나눗셈 조건 기반 점프 이동 시 각 위치별 최대 경로 합 구하기

이 튜토리얼에서는 나눗셈 조건(divisibility condition)을 만족하는 점프 이동이 가능할 때, 배열의 각 위치별로 얻을 수 있는 최대 경로 합(maximum path sum)을 구하는 방법을 알아보겠습니다.

문제 상황은 다음과 같습니다. n개의 임의의 정수로 이루어진 배열이 주어지며, 현재 위치에서 다른 위치로 점프하려면 목적지 위치가 현재 위치를 나누어 떨어지게 해야 합니다. 우리의 과제는 모든 시작 위치에 대해 이 규칙에 따라 이동할 때 만들 수 있는 경로 합의 최댓값을 계산하는 것입니다.

알고리즘 접근 방식

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• dp[i]는 i번째 위치에서 시작했을 때 얻을 수 있는 최대 경로 합을 저장합니다.
• 각 위치 i에 대해 (i+1)의 모든 약수 j를 탐색합니다. 약수에 해당하는 위치로 점프할 수 있기 때문입니다.
• 탐색한 약수 위치들의 dp 값 중 최댓값을 현재 요소의 값에 더해 dp[i]를 완성합니다.
• 약수는 √(i+1)까지의 값만 확인하면 쌍으로 모두 찾을 수 있으므로, 전체 시간 복잡도는 O(n√n)입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
// 최대 경로 합을 계산하는 함수
void printMaxSum(int arr[], int n) {
    int dp[n];
    memset(dp, 0, sizeof dp);
    for (int i = 0; i < n; i++) {
        dp[i] = arr[i];
        int maxi = 0;
        // (i+1)의 약수 위치들을 탐색
        for (int j = 1; j <= sqrt(i + 1); j++) {
            if (((i + 1) % j == 0) && (i + 1) != j) {
                if (dp[j - 1] > maxi)
                    maxi = dp[j - 1];
                if (dp[(i + 1) / j - 1] > maxi && j != 1)
                    maxi = dp[(i + 1) / j - 1];
            }
        }
        dp[i] += maxi;
    }
    for (int i = 0; i < n; i++)
        cout << dp[i] << " ";
}
int main() {
    int arr[] = { 2, 3, 1, 4, 6, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printMaxSum(arr, n);
    return 0;
}

출력 결과

2 5 3 9 8 10

결과 분석

입력 배열은 {2, 3, 1, 4, 6, 5}이며, 각 위치별 최대 경로 합은 위와 같이 계산됩니다.

예를 들어 4번째 위치(값 4)를 살펴보겠습니다. 4의 약수인 2번 위치(값 3)로 점프할 수 있고, 다시 2의 약수인 1번 위치(값 2)로 점프할 수 있습니다. 따라서 경로 4 → 3 → 2의 합인 9가 해당 위치의 최대 경로 합이 됩니다.

마찬가지로 6번째 위치(값 5)의 경우, 2번 위치(값 3)를 거쳐 1번 위치(값 2)로 이동하는 경로가 최적이므로 5 + 3 + 2 = 10이 됩니다. 반면 자기 자신 외에 나누어 떨어지게 하는 위치가 없는 1번 위치(값 2)나 3번 위치(값 1)는 점프 없이 자기 값만 반환하게 됩니다.