[C++] 백준 1912 [연속합]

문제설명

수열에서 연속된 숫자의 합의 최대값을 구해야 한다.

풀이방법

2중 for문을 활용하면 시간초과가 발생한다.
그렇기에 DP를 활용해야 한다.
DP(N)의 정의가 중요하다.
처음에 DP(N)의 정의를 N번째 수까지 숫자 중 연속된 숫자의 합의 최대값으로 정의하였다가, 점화식을 구성하는데에 어려움을 겪었다.
DP(N)을 N번째 수를 포함하는 연속된 숫자의 합의 최대값으로 정의해야 한다. 이렇게 정의하면, DP(1) ~ DP(N)까지의 결과중 최대값이 문제의 정답이 된다.
아래 그림은 DP 값을 저장하는 배열의 초기 상태이다.

DP(1)은 arr의 1번째 원소를 포함하는 연속된 숫자중 최대값이므로, 10이다.

DP(2)은 arr의 2번째 원소를 포함하는 연속된 숫자중 최대값이므로, DP(1)의 값에 arr의 2번째 원소를 더한 값과, arr의 2번째 원소를 비교하여 큰 값이 DP(2)의 값이 된다.

DP(3)은 arr의 3번째 원소를 포함하는 연속된 숫자중 최대값이므로, DP(2)의 값에 arr의 3번째 원소를 더한 값과, arr의 3번째 원소를 비교하여 큰 값이 DP(3)의 값이 된다.

쭉 넘어가서 DP(7)인 경우부터 다시 보겠다.
DP(7)은 arr의 7번째 원소를 포함하는 연속된 숫자중 최대값이므로, DP(6)의 값에 arr의 7번째 원소를 더한 값과, arr의 7번째 원소를 비교하여 큰 값이 DP(7)의 값이 된다.

DP(8)은 arr의 8번째 원소를 포함하는 연속된 숫자중 최대값이므로, DP(7)의 값에 arr의 8번째 원소를 더한 값과, arr의 8번째 원소를 비교하여 큰 값이 DP(8)의 값이 된다.
이전과 다른점은 arr의 8번째 원소가 DP(7) + arr의 8번째 원소 보다 크기 때문에 연속된 숫자를 8번째 원소인 12부터 다시 세기 시작한다.

DP(9)는 아래 그림과 같다(최대값)

DP(10)는 아래 그림과 같다.

이제 최종 cache 배열에서 최대값을 찾으면 된다.
위 그림들에서 보다시피, DP(9)이 최대값이고, 12,21이 연속된 숫자 중 합이 가장 큰 것을 알 수 있다.
이해를 돕기 위해 거의 모든 과정을 살펴보았는데, 이제 점화식을 세워보자.

점화식

$$DP(N) = max(DP(N-1) + arr[N], arr[N])$$ (단, arr의 인덱스는 1부터 시작한다고 가정)

이를 바탕으로, 아래와 같이 소스코드를 작성하였다.(arr의 index는 0부터 시작)

소스코드

#include<iostream>
#include<vector>
#include<cstring>
#include<climits>

using namespace std;

int cache[100001];
vector<int> arr;

int DP(int N){
    if(N == 1) return cache[1] = arr[0];
    int& ret = cache[N];
    if(ret != -1) return ret;
    ret = max(DP(N-1) + arr[N-1], arr[N-1]);
    return ret;
}

int main(){
    int N, result = INT_MIN;
    cin >> N;
    memset(cache, -1, sizeof(cache));
    for(int i=0; i<N; i++){
        int num;
        cin >> num;
        arr.push_back(num);
    }
    DP(N);
    for(int i=1; i<=N; i++) result = max(cache[i], result);
    cout << result;
}