[백준 C++] 1912번: 연속합

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

1912번: 연속합

 

dp 문제이다. 연속된 숫자의 합을 구하는 문제이기 때문에 dp[i]는 i로 시작하는 연속합의 최대값이라 하였을때 a[i]에서 a[i+1]을 더한값과 a[i]값을 비교하여 더 큰값을 dp[i]에 저장해 주었다. 배열 b[i]를 사용해서 수연산을 최소화 하였다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int a[100001] = { 0, };
int b[100001] = { 0, };
int dp[100001] = { 0, };
 
int main(int argc, char* argv[])
{
	int n;
	cin >> n;
	int ans = -1001;
 
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		dp[i] = b[i] = a[i];
	}
 
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1;j <= n;j++) {
			b[i] += a[j];
			if (dp[i] < b[i])
				dp[i] = b[i];
		}
		if (ans < dp[i])
			ans = dp[i];
	}
 
	cout << ans << "\n";
 
	return 0;
}

 

시간초과가 발생하였고 dp를 제대로 사용하지 못하고 있음을 깨달았다. 굳이 b[i]를 사용하지 않고 dp[i]는 i로 끝나는 연속합의 최대값으로 생각해보았다.

#include <iostream>
#include <algorithm>
using namespace std;
int a[100001] = { 0, };
int dp[100001] = { 0, };
 
#include <iostream>
#include <algorithm>
using namespace std;
int a[100001] = { 0, };
int dp[100001] = { 0, };
 
int main(int argc, char* argv[])
{
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
 
	int ans = a[0];
	dp[0] = a[0];
 
	for (int i = 1; i < n; ++i) {
		dp[i] = max(dp[i - 1] + a[i], a[i]);
		ans = max(dp[i], ans);
	}
	cout << ans << "\n";
 
	return 0;
}

 

dp의 원리를 조금 더 이해할 수 있는 문제였다고 생각한다.