[백준/c++] 13398번 - 연속합 2

[ 문제 ]

 

 

 

[ 구현 ]

 

하나의 수를 제거하는 경우와 제거하지 않는 경우를 나누어서 생각해야 한다.

 

따라서 int dp[2][100001]의 2차원 배열을 선언

 

dp[i][j]

-i=0일 때: 수를 하나도 제거하지 않은 상태로, arr[j]의 숫자를 포함시키며 만들 수 있는 연속된 수열 합의 최대값

-i=1일 때: 수를 한 가지 제거하면서, 만들 수 있는 연속된 수열의 합의 최대값(말로 딱 정의하기 애매하다)

 

점화식으로 확인하면

 

dp[0][i] = max(dp[0][i - 1] + arr[i], arr[i])
dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + arr[i])

 

 

i) dp[0][i] = max(dp[0][i - 1] + arr[i], arr[i])

 

우선 dp[0][i]의 경우이다.

 

이전까지 더해왔던 연속된 수열의 합(dp[0][i - 1])이 양수일 경우 계속 arr[i]를 더해나가는 것이 당연히 최대이다.

 

그러나 1 1 -1000 1 같은 경우를 생각해보면

dp[0][3]의 값은 -998 = max(2 + (-1000), -1000))이고

dp[0][4]에 이르게 되면, 이전까지 더해왔던 수열의 합인 -998을 버리고 그냥 4번째부터 새로 시작하는 것이 더 최대의 값(1)을 가지게 된다.

 

따라서 주의해야 할 점은 이전까지 더해온 수열의 합에 다음 수를 더한 값이 음수가 되는 경우

수열은 끊기게 되는 것이고, 따라서 dp[0][n]이 무조건 최대의 값을 가지지 않는 이유도 여기에 있다.

 

 

ii) dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + arr[i])

 

다음으로 dp[1][i]의 경우인데,

 

두 가지 상황으로 나뉜다.

 

1.앞에서 이미 수를 하나 제거하고 그 이후로부터 계속 이어서 더해오고 있는 상황

 

2.전체 수열의 i번째 수(arr[i])은 건너뛰면서 계속 수열을 이어나가고 싶은 상황(앞에서 제거한 적x)

 

1의 경우 당연하게도 앞에서 이미 제거하는 기회를 써버렸으므로 무조건 i번째 수를 더해줘야 한다.

따라서 dp[1][i-1] + arr[i]

 

2의 경우 이전까지 더해온 수열에서 i번째만 건너뛰고 이어나가고 싶은 것이므로

dp[0][i-1]값을 그대로 가진다.(이때부턴 dp[1][i]이므로 더 이상 제거가 불가능)

 

 

마지막으로 n=1인 경우, 무조건 수열에는 하나 이상의 수가 존재해야 하므로

무조건 포함시켜주는 케이스만 체크하면 문제없이 풀린다.

 

 

 

[ 코드 ]

 

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int arr[100001];
int dp[2][100001];
int ans = -1e9;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;

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

	dp[0][1] = arr[1];
	dp[1][1] = arr[1];
	ans = max(ans,arr[1]);

	for (int i = 2; i <= n; i++) {
		dp[0][i] = max(dp[0][i - 1] + arr[i], arr[i]);
		dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + arr[i]);
		ans = max({ ans,dp[0][i], dp[1][i] });
	}

	cout << ans;

	return 0;
}

 

 

[ 마무리 및 느낀 점 ]

수열의 크기가 1 이상이어야 한다는 점을 간과해서 헤맸다. 역시 문제 조건은 잘 읽어봐야 한다.

요즘 1일 1 DP문제 풀기를 하고 있는데, 뇌가 어서 말랑말랑해져서 유연한 사고를 할 수 있기를..