C++ 부분 배열에서 '최댓값 + 최솟값' 합의 최솟값 구하기

문제 설명

양의 정수 n개로 이루어진 배열이 주어졌을 때, 길이가 2 이상인 부분 배열(subarray)에서 '최댓값 + 최솟값'의 합이 가장 작아지는 경우를 찾는 것이 목표입니다.

예시

배열이 arr[] = {10, 5, 15, 7, 2, 1, 3}이라면, 부분 배열 {2, 1}에서 최댓값 + 최솟값 = 2 + 1 = 3으로 전체 중 가장 작은 값을 얻습니다.

접근 방법

• 부분 배열에 원소를 추가한다고 해서 '최댓값 + 최솟값'의 합이 줄어들지 않습니다.
• 원소를 추가할 때 배열의 최댓값은 절대 감소하지 않으며, 더 큰 값이 들어오면 오히려 증가하기만 합니다. 따라서 길이가 2인 부분 배열만 고려하는 것이 항상 최적입니다.
• 결국 인접한 두 원소로 이루어진 모든 쌍의 합을 비교하고, 그중 최솟값을 선택하면 됩니다.

구현 예제 (C++)

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

int getMinSum(int *arr, int n) {
    if (n < 2) {
        return -1;
    }
    int result = arr[0] + arr[1];
    for (int i = 1; i + 1 < n; ++i) {
        result = min(result, (arr[i] + arr[i + 1]));
    }
    return result;
}

int main() {
    int arr[] = {10, 5, 15, 7, 2, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "최소 합 = " << getMinSum(arr, n) << endl;
    return 0;
}

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

출력 결과

최소 합 = 3

복잡도 분석

• 시간 복잡도: O(n) — 배열을 한 번만 순회하며 인접한 두 원소의 합을 비교합니다.
• 공간 복잡도: O(1) — 추가 메모리 없이 상수 공간만 사용합니다.