[백준 1912] 연속 합 (DP, 점화식)

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

1912번: 연속합

임의의 수열에서 '연속'된 '몇개'의 수를 선택해서 구할 수 있는 합 중 가장 큰 값을 구하는 문제이다.

(최소 하나 이상 선택)

 

수열의 길이가 n이고

입력받은 수열을 배열 arr[100001]에 arr[1]부터 arr[n]까지 차례대로 입력받는다고 할 때, 

dp[100001]은 arr[i]를 끝값으로 가지는 연속된 수열합의 최대값을 저장한다.

 

첫번째 예제에서와 같이 입력받았을 경우를 살펴보자!

10

10 -4 3 1 5 6 -35 12 21 -1

dp[1] = 10

dp[2] = 10 + (-4) = 6

dp[3] = 10 + (-4) + 3 = 9 

여기까지 살펴보았을 때, dp[3]은 3도, -1도 아닌 9이다.

왜냐하면, arr[2]까지의 최대값이 6으로 '양수'인데, 당연히 양수 + 양수 = 더 큰 양수 이므로 dp[2] + arr[3] = dp[3]이 가질 수 있는 더 최대 양수 값이 된다.

 

이를 통해, 아래와 같은 점화식을 얻을 수 있다. (0은 값에 영향을 미치지 않으므로 포함시킨다.)

dp[i-1] >= 0 일때, dp[i] = dp[i-1] + arr[i] 

 

이어서,

dp[4] = dp[3] + arr[4]  = 9 + 1 = 10 (dp[3] > 0)

dp[5] = dp[4] + arr[5]  = 10 5 = 15 (dp[4] > 0)

dp[6] = dp[5] + arr[6] = 15 + 6 = 21 (dp[5] > 0)

 

dp[7] = dp[6] + arr[7] = 21 + (-35) = -14 (dp[6] > 0)

dp[8] = dp[7] + arr[8] = -14 + 12 = -2  ← ????

 

여기서 위의 점화식을 만족 시킬 수 없는 예외의 경우가 발생한다!

dp[7]은 arr[7]을 끝값으로 가지는 연속된 최대 합의 값인데 dp[7] + arr[8]이 arr[8]을 단독으로 갖는 경우보다 더 작은 값을 갖게된다. 

 

=> dp[7] + arr[8] < arr[8]

=> dp[7] < 0

 

위의 수식과 같이, dp[7]이 음수의 값을 가지므로 음수 + 양수 = 작아진 양수.. 가 되므로 dp[i-1]이 음수일 경우 아예 더하지 않고, arr[i] 값만을 단독으로 갖는 것이 최대값을 가질 수 있다.

 

이를통해, 아래와 같은 두번째 점화식을 얻을 수 있다.

dp[i-1] < 0 일때, dp[i] = arr[i] 

따라서 dp[i-1]값이 양수인지, 음수인지에 따라 if문을 적절히 작성하면 문제를 쉽게 풀이할 수 있다.

---

소스코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int compare(int n1, int n2) {
    return n1 > n2 ? n1 : n2;
}
int main() {
    int num;
    int result = 0;
    int arr[100001] = { 0, };
    int dp[100001] = { 0, };
 
    scanf("%d", &num);
    for (int i = 1; i <= num; i++) {
        scanf("%d", &arr[i]);
    }
 
    dp[1] = arr[1];
    result = dp[1];
    for (int i = 2; i <= num; i++) {
        if (dp[i - 1] > 0)
            dp[i] = dp[i - 1] + arr[i];
        else if (dp[i - 1] < 0)
            dp[i] = arr[i];
        result = compare(dp[i], result);
    }
    printf("%d", result);
}