BOJ 백준 13398 : 연속합 2

시작하면서

　이번 문제는 다이나믹 프로그래밍 문제이다.

BOJ 13398 - 연속합 2

​

문제 이해

​ 해당 문제는 다이나믹 프로그래밍 개념 중 메모이제이션을 사용해서 해결하는 문제이다. 조건 중에 수를 1개 제거할 수도 있고, 제거하지 않아도 되는 조건이 있기 때문에 구간합을 총 2번 구하고, 구한 구간합 중에 가장 큰 값을 답으로 출력한다.

(정수 개수의 범위가 최대 10만개이므로 무식하게 모든 경우를 다 들여다보면 O(n^2)으로 10만*10만 경우가 되어서 시간초과가 발생한다)

1. 일반적으로 0~i까지의 구간합 중 가장 큰 값을 [배열1]에 하나씩 쌓아간다.
2. 1번에서 쌓아둔 구간값 [배열1]과 쌓아둔 구간 값에서 한 개의 값을 뺐을 때의 구간값을 비교해서 더 큰 값을 [배열2]에 넣어준다.
3. [배열1]과 [배열2]를 모두 돌면서 가장 큰 값을 답으로 출력한다.

​

해결

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

	vector<int> numbers, continuousSum[2];
	int n, result = 0;

	cin >> n;

	numbers.resize(n);
	continuousSum[0].resize(n);
	continuousSum[1].resize(n);

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

	// 1. 일반 구간합
	continuousSum[0][0] = numbers[0];
	for (int i = 1; i < n; i++)
	{
		continuousSum[0][i] = max(numbers[i], continuousSum[0][i - 1] + numbers[i]);
	}

	// 2. 하나를 제외한 구간합
	continuousSum[1][0] = numbers[0];
	for (int i = 1; i < n; i++)
	{
		continuousSum[1][i] = max(continuousSum[0][i - 1], continuousSum[1][i - 1] + numbers[i]);
	}

	// 3. 1/2번 경우 중에 가장 큰 구간합을 찾음
	result = continuousSum[0][0];
	for (int i = 0; i < n; i++)
	{
		result = max(continuousSum[0][i], result);
		result = max(continuousSum[1][i], result);
	}

	cout << result << "\n";

	return 0;
}

​

마치며

　구간합에 관한 문제를 자주 접하지 않아서 초반에 힘들었다. 검색을 통해 구간합 구하는 방법을 보고 해결할 수 있었다. 구간합을 배우는 좋은 문제!