13398 연속합2 (동적계획법) [Gold V]

13398번: 연속합 2 (acmicpc.net)

 

입력받은 n개의 임의의 수열 중에 연속된 수로 구할 수 있는 합이 가장 큰 수를 구하는 문제입니다.

이때 수열에서 수를 하나 제거할 수 있습니다.

 

풀이법

 

수열에서 수를 하나 제거할 수 있다는 조건을 빼고 연속된 수의 합을 구하는 방법을 생각해 보겠습니다.

 

예시

int Array[10] = {10, -4, 3, 1, 5, 6, -35, 12, 21, -1};
int L[10];

 

10개의 수가 있을 때 연속된 수의 가장 큰 합을 구하는 방법은

0번 인덱스부터 9번 인덱스까지 숫자가 더 커질 수 있게 더해가는 것입니다.

 

코드 표현

L[i] = max(Array[i], L[i - 1] + Array[i]);
L = {10, 6, 9, 10, 15, 21, -14, 12, 33, 32};

 

이후 완성된 Result 배열에서 가장 높은 수가 연속된 수의 합중 가장 큰 수가 됩니다

 

하지만 해당 문제에는 변수가 하나 존재합니다.

( 수열에서 수를 하나 제거할 수 있다 )

하지만 잘 생각해보면 굉장히 쉽게 해결할 수 있는 문제입니다.

 

수열중 하나를 제거할 수 있다는 것은 index 1개를 건너 뛰고 붙어있는 연속된 수 두개를 붙일 수 있다는 의미입니다.

즉 정답은 (0 ~ 9번 방향으로 만들어진 연속된 수의 합) + (9  ~1번 방향으로 만들어진 연속된 수의 합) 이라고 생각할 수 있겠습니다.

 

9 ~ 0번 방향으로 만들어진 연속된 수의 합

R[i] = max(Array[i], R[i + 1] + Array[i]);
R = {21, 11, 15, 12, 11, 6, -2, 33, 21, -1};

 

 

이제 수를 하나 제거했다는 의미에서 1개 인덱스를 띄우고

배열의 값들을 더해가며 가장큰 값을 찾아줍니다.

int result = 0;	
for (int i = 1; i < N - 1; i++) {
    int temp = L[i - 1] + R[i + 1];
    result = max(result, temp);
}

 

 

정답코드

#include <iostream>
#include <vector>

using namespace std;
 
static int N;
static vector<int> A, L, R;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	 
	cin >> N;
	A.resize(N);

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

	L.resize(N);
	L[0] = A[0];
	int result = L[0];

	for (int i = 1; i < N; i++) {
		L[i] = max(A[i], L[i - 1] + A[i]);
		result = max(result, L[i]);
	}
	
	R.resize(N);
	R[N - 1] = A[N - 1];
	for (int i = N - 2; i >= 0; i--) {
		R[i] = max(A[i], R[i + 1] + A[i]);
	}

	for (int i = 1; i < N - 1; i++) {
		int temp = L[i - 1] + R[i + 1];
		result = max(result, temp);
	}

	cout << result;
}