[백준] 13398-연속합2(C++)

문제링크:www.acmicpc.net/problem/13398

13398번: 연속합 2

 

쉬운 dp 문제였습니다.

 

조건은 두가지입니다. 

1. 수열에서 수를 하나 제거할 수 있다.

2. 제거하지 않아도 된다.

 

우선 제거하지 않을때는 

if (dp[i - 1][0] > 0)
dp[i][0] = arr[i] + dp[i - 1][0];
else
dp[i][0] = arr[i];

로 쉽게 구할 수 있습니다.

 

그리고 하나의 수를 제거할 때는 

1) 현재 자신을 제거한 값이 큰지,

2) 이전에 제거한 값 + 현재값이 큰지

비교합니다.

 

정답코드입니다.

너무 쉬워서 점화식은 따로 기재하지 않았습니다.

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

/* 
제거 한경우 제거 안한 경우 

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

0: 10 6 9 10 15 21 -14 -2 19 18   
1: 0 10 13   
현재 자신에서 뺀값이라 이미 빠진값이랑 비교해서 더큰값으로 넣는다. 
*/

int dp[100001][2] = { 0 };
int arr[100001] = { 0 };
int n = 0, result = -1000000000;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	dp[1][0] = arr[1];

	for (int i = 2; i <= n; i++) {
		if (dp[i - 1][0] > 0)
			dp[i][0] = arr[i] + dp[i - 1][0];
		else
			dp[i][0] = arr[i];
	}
	
	dp[1][1] = 0;

	for (int i = 2; i <= n; i++) {
		//1. 자신을 제외했을때 값과 이미 제한값을 비교
		int a = dp[i - 1][0]; //자신을 제외했을때
		int b = dp[i - 1][1] + arr[i];
		dp[i][1] = max(a, b);
	}

	for (int i = 2; i <= n; i++) {
		if (result < dp[i][0]) result = dp[i][0];
		if (result < dp[i][1])	result = dp[i][1];
	}
	if (result < dp[1][0]) result = dp[1][0];




	if (n == 1) cout << arr[1] << endl;
	else cout << result << endl;
	return 0;
}