[백준 / BOJ] 1912번: 연속합

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

1912번: 연속합

 

 

---

 

코드

---

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

int ar[100000];
int dp[100000];

int main() {
	int n, res;
	cin >> n;

	for (int i = 0; i < n; i++) cin >> ar[i];

	dp[0] = ar[0];
	res = dp[0];
	for (int i = 1; i < n; i++) {
		dp[i] = max(dp[i - 1] + ar[i], ar[i]);
		res = max(res, dp[i]);
	}
	cout << res;
	return 0;
}

 

 

 

---

 

 

동적 계획법으로 풀 수 있는 문제이며, 단순하게 생각하면 쉽다. 

가장 큰 연속 합을 구해야 한다. 연속해서 값을 더하는데, 대체 어떤 수에서 연속으로 더하는 것을 멈춰야 할까?

dp[i]를 i번째 수 직전 구간부터 i번째 수까지의 연속 합의 값이라고 하자.

(dp[i-1] + i번째 수)가 i번째 수보다 크다면 dp[i]에 (i-1번째 수의 합 + i번째 수)를 저장한다. (i-1번째 수의 합 + i번째 수)가 i번째 수보다작다면 연속으로 더하지 않고 끊어서, i번째 수부터 다시 연속 합을 시작하는 것이 더 큰 연속 합 값을 갖게 될 것이다. 따라서 dp[i]에 i번째 수를 저장한다. 이 개념이 끝이다. dp에는 각각 구간별로 가장 큰 연속 합의 값이 저장되어 있을 것이기 때문에 가장 큰 값을 기억하기 위한 변수 res를 선언하여 n번째 수까지 dp계산이 모두 끝난 후 res를 반환하면 된다.