C++ / 1912 / 연속합 ( 다이나믹 프로그래밍 )

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

문제 요약

n개의 정수로 이루어진 임의의 수열이 주어집니다. 우리는 이중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 합니다.
단 수는 한 개 이상 선택해야 합니다.

문제 풀이

1. 수열을 입력받습니다.
2. dp 함수를 만듭니다. dp 함수에서는 수별로 최댓값을 담은 배열을 만듭니다.
3.  이 문제의 점화식은
 
v = { 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 }
 
라는 수열이 있을때 여기서 정답은 12 + 21 = 33 입니다.
21이라는 인덱스 기준으로 직전의 정답 배열 까지의 최댓값과 자신을 더한 값이라고 할 수 있습니다.
따라서 직전항이  없는 1번째 만 초기값을 주고 그 후로는 반복문에서 이전항합 + 현재항 vs 현재항만 비교 하였을때 더 큰값을 정답 배열에 넣어주면 각 숫자까지의 나올 수 있는 최댓값을 구할 수 있습니다.
 
p = { 10, 6, 9, 10, 15, 21, -14, 12, 33, 32 } 
 
위의 수열에서의 각 숫자까지의 최댓값
 
4.  메인 함수에서는 이 정답 배열에서 가장큰 값을 출력 해주면 됩니다.
 
 

주의할 점

이 문제로 dp 문제이기 때문에 점화식을 찾는것이 중요했습니다.
바로 전날에 dp 문제를 풀었었기 때문에 비교적 수월하게 풀었던 것 같습니다.
다만 푸는 과정에서 비교하는 값으로 이전항 + 현재항으로 처음에 썼었는데
이는 한개의 항만 사용해야 하는 경우같은 예외가 생길 수 있기 때문에 틀린 답이 되었었습니다.

코드 

#include<iostream>
#include<vector>

using namespace std;

int p[100001];
vector<int> v;
int n;
int sum = 0;
void dp()
{
	p[1] = v[1];
	for (int i = 2; i <= n; i++)
	{
		// 이전항합 + 현재항
		int a = p[i - 1] + v[i];
		// 현재항만
		int b = v[i];
		// 이전항합 + 현재항중 현재항이 더 큰쪽으로 초기화
		p[i] = max(a, b);
	}
}
int main()
{
	cin >> n;
	v.push_back(0);
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		v.push_back(a);
	}
	dp();	
	int max = -1001;
	for (int i = 1; i <= n; i++)
	{
		if (max < p[i])
		{
			max = p[i];
		}

	}


	cout << max;
	return 0;
}

반응형

예제 1

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

결과 1

예제 2

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

결과 2

예제 3

5
-1 -2 -3 -4 -5

결과 3