[알고리즘] 백준 1912번: 연속합 (C++), DP에 조건 따지기란 점화식의 일부

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

1912번: 연속합

요즘 블로그 임시저장 기능을 너무 많이 사용하는 거 같아서 조금 정리 차원에서 글을 쓴다.

핑계를 덧붙이자면 임시저장 글 중에 '가장 긴 증가하는 부분 수열 (LIS)'도 있는데 그 문제 포스팅하기 전에 이거 먼저 해두면 좋을 거 같아서 먼저 포스팅한다.

 

우선 기본적으로 나오는 점화식은

cache[i] = cache[i - 1] + arr[i];

다음과 같다. 하지만, 무작정 더하면 최댓값을 도출하지 못한다.

양수만 나온다면 다 더해도 최댓값이 도출되지만 문제에서는 음수도 존재한다고 알려주고 있다.

예를 들어

1, 1, 101, 102

같은 수열이 주어지면 다 더하면 최댓값이다.

1, -2, 101, 102

라면 말이 달라진다.

수열의 값을 다 더했을 때 나오는 값은 202이지만

도출되어야 하는 값은 203 (101 + 102)이다.

즉, 이런 결론이 나오게 된다.

-2까지 더했을 때 나오는 값은 -1이다.

그런데 여기서 101을 더하는 것과 -1을 버리고, 101부터 시작을 하기 위해 101을 가져가는 것이 점화식에 추가되어야 할 조건이다.

 

>> 이전까지 더한 값이 음수라면 최댓값을 찾는 입장에서 그 전까지의 합은 버려야 한다.

 

점화식은 늘 즉각적인 조건을 요구한다는 것을 명심하자.

 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int arr[100001] = { 0, };
int cache[100001] = { 0, };

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int idx;
		cin >> idx;
		arr[i] = idx;
	}

	cache[1] = arr[1];
	for (int i = 2; i <= n; i++) {
		if (cache[i - 1] + arr[i] >= arr[i]) {
			cache[i] = cache[i - 1] + arr[i];
		}
		else {
			cache[i] = arr[i];
            // arr[i]가 음수라서가 아니라
            // 애초에 cach[i - 1] + arr[i]가 음수라면
            // 최댓값을 도출하는데에 있어서 더하지 않고
            // arr[i]부터 시작하는 것이 맞다.
		}
	}

	int max = -1001;
	for (int i = 1; i <= n; i++) {
		if (cache[i] > max) {
			max = cache[i];
		}
	}
	cout << max;

	return 0;
}

---

웬만한 DP 문제는 다 업 솔빙을 해봐야겠다.