백준 1912번 연속합

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

이 문제는 그저께 계단 오르기처럼 점화식을 세우기 보단.. 예시 입력으로 부터 규칙을 찾아내려 하였다.

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

  

처음엔 실수 했던 것이, 양수만 모두 더하는 경우만 생각하였었다.

즉, 위 예제에서 2번째는 음수(-4)이므로 더하지 않고, 3번째(3) ~ 6번째(6)까지만 더한 값만을 고려한다거나, 12 + 21만 고려한다거나 하는 경우만 생각했다.

위 예제에선 운 좋게 답은 맞았을 지 몰라도, 12와 21이 1과 2라면 답은 달라지게 된다. 

10
10 -4 3 1 5 6 -35 1 2 -1

그 이유는

10 -4 +3 +1 +5 +6 = 21인데,

10 -4 +3 +1 +5 +6 = 15이기 때문이다.

처음 생각대로 양수만 더했다면 21이 답이지만, 15를 출력하는 결과가 나왔을 것이다.

때문에 dp[n] = n번째에서 가질 수 있는 최대 값으로 설정하고 점화식을 작성하려 하였다.

위 예제에서 보면

dp[0] = 10 이며,

dp[1] 은 이전 값( dp[0] ) + 현재 값 ( nums[1] ) = 10 - 4 = 6

dp[2] 는 이전 값( dp[1] ) + 현재 값 ( nums[2] ) = 6 + 3 = 9

dp[3] 은 이전 값( dp[2] ) + 현재 값 ( nums[3] ) = 9 + 1 = 10

dp[4] 은 이전 값( dp[3] ) + 현재 값 ( nums[4] ) = 10 + 5 = 15

dp[5] 은 이전 값( dp[4] ) + 현재 값 ( nums[5] ) = 15 + 6 = 21

dp[6] 은 이전 값( dp[5] ) + 현재 값 ( nums[6] ) = 21 - 35 = -14

여기서 중요한 규칙이 나오게 된다.

dp[7] 은 이전 값( dp[6] ) + 현재 값 ( nums[7] ) = -14 + 1 = -13 인데, 이는 현재 값( nums[7] ) 보다 작은 값이기 때문에 max( -13, 1 ) 인 1을 값으로 가져야 한다.

즉, dp[n]을 구하는 점화식은 

1. 1단계 전까지 최대로 가졌던 연속합 + 현재 값
2. 현재 값

2가지 중 최대값을 선택하면 된다. 이를 식으로 나타내면,

dp[n] = max(dp[n-1] + nums[n], nums[n]) 로 표현 될 수 있을 것이다.

끝까지 위의 점화식으로 dp[n]을 구한 뒤, 마지막 답을 도출 할 땐 dp 배열 중에서 최대값을 결과로 출력하면 된다.

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
   int n = 0, result = -1000;
   int nums[100001] = {0, };
   int dp[100001] = {0, };
   
   cin >> n;
   for(int i = 0; i < n; ++i) {
       cin >> nums[i];
   }
   
   dp[0] = nums[0];
   
   for(int i = 1; i < n; ++i) {
       dp[i] = max(dp[i-1] + nums[i], nums[i]);
   }
   
   for(int i = 0; i < n; ++i) {
       result = max(result, dp[i]);
   }
   
   cout << result << endl;
   return 0;
}