C++로 배열 요소를 더하고 빼며 만들 수 있는 최대값 구하기

문제 설명

정수로 이루어진 배열과 시작 숫자, 그리고 상한값(max limit)이 주어졌을 때, 배열 요소들을 활용해 만들 수 있는 최대값을 구하는 것이 이번 문제의 목표입니다.

배열을 처음부터 끝까지 순회하면서 각 단계에서 현재 요소를 이전 단계의 결과에 더하거나 뺄 수 있습니다. 단, 다음 두 조건을 반드시 지켜야 합니다.

결과는 어느 시점에서도 0보다 작아서는 안 됩니다.
결과는 주어진 최대값을 초과해서는 안 됩니다.

인덱스 0에서는 이전 결과가 주어진 숫자(number)라고 가정하며, 어떤 경우에도 답을 구할 수 없다면 -1을 출력합니다.

예를 들어 arr[] = {3, 10, 6, 4, 5}, number = 1, max value = 15일 때, 아래 순서대로 연산을 수행하면 결과는 9가 됩니다.

1 + 3 + 10 – 6 – 4 + 5

알고리즘

이 문제는 재귀(recursion)를 이용해 해결할 수 있습니다.

각 인덱스 위치에는 두 가지 선택지가 있습니다. 지금까지 계산된 값에 현재 배열 요소를 더하거나, 현재 배열 요소를 빼는 것입니다.
인덱스 0부터 시작하여 주어진 숫자에 arr[0]을 더하거나 뺀 뒤, 갱신된 값을 가지고 다음 인덱스를 재귀적으로 호출합니다.
배열 전체를 순회하면, 갱신된 값을 지금까지 구한 전체 최대값과 비교하여 더 큰 값을 저장합니다.

C++ 구현 예제

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

void getMaxValue(int *arr, int n, int num, int maxLimit, int idx, int& result){
    if (idx == n) {
        result = max(result, num);
        return;
    }
    if (num - arr[idx] >= 0) {
        getMaxValue(arr, n, num - arr[idx], maxLimit, idx + 1, result);
    }
    if (num + arr[idx] <= maxLimit) {
        getMaxValue(arr, n, num + arr[idx], maxLimit, idx + 1, result);
    }
}

int getMaxValue(int *arr, int n, int num, int maxLimit){
    int result = 0;
    int idx = 0;
    getMaxValue(arr, n, num, maxLimit, idx, result);
    return result;
}

int main(){
    int num = 1;
    int arr[] = {3, 10, 6, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int maxLimit = 15;
    cout << "Maximum value = " << getMaxValue(arr, n, num, maxLimit) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Maximum value = 9

복잡도 분석

시간 복잡도: O(2ⁿ) — 각 인덱스마다 '더하기'와 '빼기' 두 가지 분기가 발생하므로, 최악의 경우 모든 경우의 수를 탐색하게 됩니다.

공간 복잡도: O(n) — 재귀 호출의 최대 깊이가 배열의 길이와 같기 때문입니다.

배열의 길이가 커질 경우에는 메모이제이션(memoization)이나 동적 계획법(DP)을 적용해 중복 탐색을 줄이는 최적화를 고려할 수 있습니다.