[baekjoon 1912] 연속합 - DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/1912

1912번: 연속합

문제는 주어진 수열에서 연속으로 나열된 숫자의 합이 최대가 되는 경우(결괏값은 합의 최댓값)를 찾는 것이다.

 

점화식을 세우기 위해서 여러 케이스를 생각해보았다.

일단 합의 최댓값이 되려면 더해지는 수가 음수면 안될 것 같았다.

-> 하지만 이 i번째 음수를 포함하고 i+1번째 수를 더해서 최댓값이 나올 수 있다.

-> i+1을 더해서 최댓값이 성립되려면 i번째까지의 누적합이 양수인 경우다.

(i번째 누적합이 음수일 경우 누적 합의 최댓값은 음수를 더하지 않은 i+1 값 그 자체가 될 것이다.)

 

즉, dp배열에 i번째의 누적합을 저장하되 저장할 때 비교는 max(i번째 누적합 + i+1번째 수, i+1번째 수) 면 되겠다.

누적합이 음수가 아니면 자연스레 1이라도 더해진 값이 연속 최댓값이 될 것이다.

 

 + i번째까지 누적합이 계산된 경우, 다음 i+1번째 누적합을 어떻게 구할까? 를 생각해보면 도움이 된다.

 + 시간제한은 1초로 O(N^2)로 풀 경우(모든 경우를 다 더해서 비교해주는 경우) 시간 초과가 난다.

#include <iostream>
using namespace std;

int arr[100001], dp[100001], n;

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

	dp[0] = arr[0];

	int mx = dp[0];

	for (int i = 1; i < n; i++) {
		dp[i] = max(dp[i-1] + arr[i], arr[i]);
		if (mx < dp[i])
			mx = dp[i];
	}

	cout << mx;

}

dp 너무 어렵다.. 최대한 짧은 기간 동안 많이 풀어서 감을 터득해야 할 듯하다.