Silver II 난이도의 이 문제는 동적 계획법(Dynamic Programming)을 이용하여 주어진 정수 배열에서 연속된 부분 배열의 합 중 최댓값을 찾는 문제입니다. C++ 언어를 사용하여 4ms의 실행 시간과 2804KB의 메모리로 해결되었습니다.

백준 1912: 연속합

문제 소개

문제 번호: 1912
문제명: 연속합
난이도 (티어): Silver II
사용 언어: C++
실행 시간: 4 ms
메모리: 2804 KB
문제 요약: 정수만으로 이루어진 1차원 배열이 주어졌을 때, 연속된 부분 배열의 합 중 가장 큰 값을 출력하는 문제입니다.

접근 방법

이 문제는 "최대 부분 배열 합" 또는 "연속 부분 배열 합"과 같이 불리는 고전적인 동적 계획법 문제입니다. 문제의 핵심은 각 원소에서 끝나는 최대 연속 부분합을 계산하고, 그중 최댓값을 찾는 것입니다.

제가 선택한 방법은 동적 계획법(Dynamic Programming)입니다. DP를 사용하면 중복 계산을 피하고 효율적으로 최적해를 찾을 수 있기 때문입니다. 특히, 각 인덱스 i에서 끝나는 연속 부분 배열의 최대 합을 dp[i]로 정의하는 방식을 사용했습니다.

풀이 과정

입력 받기: 먼저 배열의 크기 N을 입력받고, N개의 정수를 저장할 vector<int> a(N)를 선언하여 입력받습니다.
DP 배열 초기화: vector<int> dp(N)를 선언하여 각 인덱스에서 끝나는 최대 연속 부분합을 저장할 공간을 만듭니다.
첫 번째 원소 처리: dp[0]은 첫 번째 원소 a[0] 자체입니다. 따라서 dp[0] = a[0]으로 초기화하고, 전체 최댓값 ans 또한 dp[0]으로 초기화합니다.
DP 점화식 적용: i가 1부터 N-1까지 반복하면서 dp[i]를 계산합니다. dp[i]는 두 가지 경우 중 더 큰 값으로 결정됩니다.
- a[i] 자체로 새로 시작하는 경우 (이전까지의 합이 음수여서 더하는 것보다 낫다고 판단될 때)
- dp[i-1] + a[i] (이전 원소에서 끝나는 최대 연속 부분합에 현재 원소를 더하는 경우)
  즉, dp[i] = max(a[i], dp[i-1] + a[i]) 입니다.
최대값 갱신: 매 반복마다 ans = max(ans, dp[i])를 통해 지금까지 찾은 모든 dp[i] 값들 중 최댓값을 갱신합니다.
결과 출력: 모든 N개의 원소에 대해 계산이 끝나면, 최종적으로 ans에 저장된 최대 연속 부분합을 출력합니다.

핵심 아이디어: 현재 위치 i에서 끝나는 최대 연속합은, i-1에서 끝나는 최대 연속합에 a[i]를 더한 값과 a[i] 자체 중 더 큰 값입니다. 이 아이디어를 통해 이전 상태의 값을 활용하여 현재 상태의 최적해를 효율적으로 구할 수 있습니다.

주의할 점: 모든 입력 숫자가 음수일 경우, 최대 연속합은 가장 큰 음수 하나가 됩니다. 이 경우에도 DP 점화식 dp[i] = max(a[i], dp[i-1] + a[i])는 올바르게 동작하며, ans가 최댓값을 잘 유지하게 됩니다.

코드 설명

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

int main() {
    // 입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; // 배열의 크기
    cin >> N;

    vector<int> a(N); // 입력 배열
    for (int i = 0; i < N; i++) {
        cin >> a[i]; // 배열 요소 입력
    }

    // dp[i] = i번째 원소에서 끝나는 "최대 연속 부분합"
    vector<int> dp(N);
    
    // 첫 번째 원소는 자기 자신이 최대 연속 부분합
    dp[0] = a[0];
    int ans = dp[0]; // 전체 최대 연속 부분합 (초기값은 첫 번째 원소)

    // 1번 인덱스부터 N-1번 인덱스까지 순회
    for (int i = 1; i < N; i++) {
        // 현재 원소 a[i]에서 새로 시작하는 경우 vs 이전까지의 최대 연속합에 a[i]를 더하는 경우
        dp[i] = max(a[i], dp[i-1] + a[i]);
        
        // 현재까지 찾은 최대 연속 부분합 갱신
        ans = max(ans, dp[i]);
    }

    // 최종 최대 연속 부분합 출력
    cout << ans << "\n";
    return 0;
}

ios::sync_with_stdio(false); cin.tie(nullptr);: C++ 표준 라이브러리의 입출력 스트림과 C 스타일 입출력 스트림을 동기화하지 않고, cin과 cout이 tie된 nullptr을 사용함으로써 입출력 속도를 최적화합니다.
vector<int> a(N);: 입력으로 주어지는 N개의 정수를 저장할 벡터입니다.
vector<int> dp(N);: dp[i]는 i번째 인덱스에서 끝나는 연속 부분합의 최댓값을 저장합니다.
dp[0] = a[0];: 배열의 첫 번째 원소로 끝나는 연속합은 자기 자신뿐이므로 a[0]으로 초기화합니다.
ans = dp[0];: 최종 결과로 출력할 최댓값 ans를 dp[0]으로 초기화합니다.
dp[i] = max(a[i], dp[i-1] + a[i]);: 이 줄이 동적 계획법의 핵심입니다. i번째 원소에서 끝나는 최대 연속합은, a[i] 자체로 새로 시작하는 경우와 i-1번째 원소에서 끝나는 최대 연속합에 a[i]를 더하는 경우 중 더 큰 값입니다.
ans = max(ans, dp[i]);: 현재 계산된 dp[i] 값이 기존의 최댓값 ans보다 크다면 ans를 갱신합니다.

복잡도 분석

시간 복잡도: 배열의 크기 N에 대해 한 번의 선형 스캔을 통해 DP 테이블을 채우고 최댓값을 찾습니다. 따라서 시간 복잡도는 O(N) 입니다.
공간 복잡도: 입력 배열 a와 DP 배열 dp를 저장하기 위해 O(N)의 공간이 필요합니다.

배운 점

이 문제를 통해 동적 계획법의 기본적인 아이디어와 적용 방법을 다시 한번 명확히 할 수 있었습니다. 특히 "현재 상태를 이전 상태들의 값으로 표현한다"는 DP의 핵심을 "현재 원소 a[i]에서 끝나는 최대 연속합은 a[i] 자체 또는 dp[i-1] + a[i] 중 최댓값"이라는 점화식으로 구체화하는 과정이 중요했습니다.

또한, 모든 입력이 음수일 때도 올바르게 동작하는 알고리즘의 견고성을 확인할 수 있었습니다. 이 문제에서 사용된 DP 접근 방식은 '최대 연속합'을 구하는 것 외에도, 배열 내에서 어떤 조건을 만족하는 연속된 부분 배열의 합이나 길이를 구할 때도 응용될 수 있을 것입니다.

다른 문제에 적용할 수 있는 팁

관련 문제: Kadane's Algorithm은 이 문제를 푸는 표준적인 알고리즘이며, 최대 부분 배열 합 문제의 일반적인 해결책입니다.
변형: 만약 "최소 연속합"을 구해야 한다면, max 대신 min을 사용하고 초기값 설정 등에 주의를 기울이면 비슷한 방식으로 해결할 수 있습니다.
2차원 배열: 2차원 배열에서의 최대 직사각형 부분합 문제는 이 1차원 최대 연속합 문제를 여러 번 풀어 해결하는 방식으로 확장될 수 있습니다.