[백준] 13398번 : 연속합 2

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

13398번: 연속합 2

DP문제 이다. 

연속된 수열의 최대합을 구하는 문제지만, 수열중 숫자 1개는 삭제 가능하다는 추가 조건이 있다. 

따라서, 삭제 기회를 쓰는경우와 안쓰는 경우로 나눈 이차원 배열을 사용하였다.

 

dp[i][0] : 0부터 i번째까지 존재하는 연속된 수열의 최대합 & 삭제 기회 남음

• 삭제 기회를 사용하면 안되기 때문에 i-1번째까지 최대합에 현재 값을 더한것과 현재값부터 다시 시작하는 경우 두가지 경우를 비교해야한다.
• max(dp[i - 1][0] + a[i], a[i])

dp[i][1] : 0부터 i번째까지 존재하는 연속된 수열의 최대합 & 삭제 기회 없음 

• 삭제 기회를 전에 사용했거나 지금 삭제 해야하므로 삭제기회를 사용한 i-1번쨰까지의 최대합에 현재 값을 더하거나 삭제기회를 사용하지 않은 i-1번째까지의 최대합을 그대로 들고오는 두가지 경우를 비교해야한다.
• max(dp[i - 1][1] + a[i], dp[i - 1][0])

 

코드는 다음과 같다.

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

int N;
int a[100000];
int dp[100000][2]; //[][0] -> 아직 삭제 x  & [][1] -> 삭제 사용
int result;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	result = a[0];
	dp[0][0] = a[0];
	for (int i = 1; i < N; i++) {
		dp[i][0] = max(dp[i - 1][0] + a[i], a[i]); 
		dp[i][1] = max(dp[i - 1][1] + a[i], dp[i - 1][0]); 
		result = max({ result, dp[i][0], dp[i][1] });
	}
	cout << result << endl;
}