[백준 알고리즘] 1912번: 연속합

https://www.acmicpc.net/problem/1912

문제

문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력
첫째 줄에 답을 출력한다.

풀이

처음에 문제를 보고 정답률이 너무 낮아서 어려운 문제다 싶었는데, 생각보다 어렵지는 않았다. 아마도 문제를 너무 쉽게 생각해서 방심한 것 같다.

문제를 읽었을 때, 뭐지? 그냥 음수빼고 최대 연속합 구하면 되는거 아닌가? 싶었다. 근데 그런 문제의 정답률이 26%일리는 없지 않는가! 그래서 잘 생각해보았다. 음수가 끼어있더라도 최대 합이 될 수 있는 경우를 생각해보았는데, 너무나 당연했다.

DP 문제를 풀 때는 최대한 문제를 제일 작은 문제로 쪼개어서 생각해보려고 하는데, 이번에 문제를 보고 든 생각은 이렇다. 만약 현재 위치 바로 이전 숫자가 음수라면, 그 수까지의 최적해와 지금 자기 숫자를 비교해보면 되지 않을까 싶었다. 왜냐하면 양수가 연속으로 나올 경우에는 항상 그 두 숫자의 합이 최고의 연속합이 될 수 밖에 없다.

따라서 음수가 끼어있을 경우에 최고의 연속합을 고려하면 음수까지 모두 더한 값과 이번 값을 더하거나, 이번 값을 새로운 연속합의 시작으로 만드는 두 가지 경우의 수를 생각할 수 있었다.

이 논리를 수식으로 세워보면 이렇다. 어떤 수열 A와 i 번째 위치에서의 최적해를 저장하는 수열 dp가 있을 때,

이 수식을 코드로 적용하여 테스트를 돌리고 AC를 받았다. 맞은 사람의 코드를 보니 내가 사용하는 메모리의 절반만 사용하고 푼 경우도 많았는데 다른 사람의 코드를 보면서 공부를 해야겠다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int dp[100001];

int main()
{
    int A[100001];
    int n;

    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }

    dp[0] = A[0];
    int result = A[0];

    for (int i = 0; i < n; i++)
    {
        if (A[i - 1] < 0)
            dp[i] = max(A[i], A[i] + dp[i - 1]);
        else
            dp[i] = A[i] + dp[i - 1];

        result = max(result, dp[i]);
    }

    cout << result;
}