백준 1912번 연속합 [DP] :: 마이구미

이번 글은 백준 알고리즘 1912번 문제 "연속합" 을 다뤄본다.

일단 문제를 보자.

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

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

문제는 쉽게 이해할 수 있다.

연속되는 수들을 골라 최대의 합이 되는 수를 고르면 된다.

사이트에서 알고리즘 분류를 보면 알다시피 동적계획법으로 풀기를 권장하는 문제이다.

어떻게 점화식을 만들 수 있을까?

점화식에 앞서 함정만 파악하면 쉽게 문제를 풀 수 있다.

임의의 수열 7 8 -9 10 주어졌을 때, 최대의 합은 얼마일까?

정답은 7과 8을 연속으로 선택함으로써, 15라고 생각하면 문제의 함정에 빠지는 것이다.

7,8,-9,10 연속된 수를 전부 선택한다면 합은 16이 된다.

즉, 음수를 선택하더라도 합이 더 큰 경우가 나올 수 있다는 얘기이다.

조금 더 생각해보면, 이 문제의 해결법을 쉽게 파악할 수 있다.

연속된 수를 선택하면서 합을 구하는 것이므로, 쉽게 점화식을 찾을 수 있다.

dp[n] = dp[n] + dp[n-1] 

n번째 이전의 합과 n번째 수를 더하면 n번째까지의 합이 나오므로 위와 같은 점화식을 도출할 수 있다.

그리고 2가지만 염두하면 된다.

1. dp[i-1] > 0

  - 이전의 합이 음수라면 선택할 필요 없이 현재부터 다시 선택해나가면 된다. 

2. dp[i] + dp[i-1] > 0

  - 이전의 합과 현재의 수를 더한 값이 음수라면 선택할 필요가 없다. 

 for(int i=2;i<=n;i++) {

    if (dp[i-1] > 0 && dp[i] + dp[i-1] > 0) {
        dp[i] += dp[i-1];
    } 

    if (max < dp[i]) {
        max = dp[i];
    }

}

하나의 반복문으로도 문제를 해결할 수 있다.

더 이해를 돕기 위해 Github 사이트를 통해 전체 소스를 확인하길바란다.

이만 안녕.

백준 알고리즘 사이트 1912번 연속합 문제

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

백준 1912번 연속합 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/dp/1912.java