백준 13398번 연속합 2 - C++(cpp) 풀이

---

 

1. dp[idx][did_remove] = 숫자 제거 여부가 did_remove일 때 idx번째 수로 시작하는 최대 연속합
2. dp[idx][1] = max(arr[i], arr[i]+dp[i+1])
3. dp[idx][0] = max(arr[i], arr[i]+dp[i+1][0], arr[i]+dp[i+2][1])

 

1. dp[idx][did_remove] = 숫자 제거 여부가 did_remove일 때 idx번째 수로 시작하는 최대 연속합

 연속합은 재귀적으로 생각할 수 있다. 또한 숫자를 최대 한 개까지 제거할 수 있으므로 dp[idx][did_remove]를 숫자 제거 여부가 did_remove일 때 idx번째 수로 시작하는 최대 연속합이라고 정의하자.

 

2. dp[idx][1] = max(arr[i], arr[i]+dp[i+1])

 did_remove = 1인 경우, 즉 기존에 숫자를 제거한 이력이 있는 경우 더이상 수를 제거할 수 없다. 따라서 arr[i]번째 수에서 끝내거나, 다음 수인 arr[i+1]까지 연속되도록 하는 두 가지 경우가 있다. 이 두 가지 경우 중 더 큰 값을 갖는 경우를 택한다.

 

3. dp[idx][0] = max(arr[i], arr[i]+dp[i+1][0], arr[i]+dp[i+2][1])

 did_remove = 0인 경우, 즉 기존에 숫자를 제거한 이력이 없는 경우 수를 제거할 수도 있다. arr[i]번째 수에서 끝내거나, 다음 수인 arr[i+1]까지 연속되도록 하거나, 다음 수를 제거하고 다다음 수인 arr[i+2]와 연속되게 하는 세 가지 경우가 있다. 이 중 가장 큰 값을 갖는 경우를 택하면 된다.

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

typedef long long ll;

const int MAX = 100002, MIN = -987654321;
int N;
ll arr[MAX], dp[MAX][2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i=0; i<N; i++) cin >> arr[i];
    
    for (int i=N-1; i>=0; i--) {
        for (int j=0; j<2; j++) {
            dp[i][j] = max(arr[i], arr[i]+dp[i+1][j]);
            if (j == 0) dp[i][j] = max(dp[i][j], arr[i]+dp[i+2][1]);
        }
    }
    
    ll ans = MIN;
    for (int i=0; i<N; i++) ans = max(ans, dp[i][0]);
    
    cout << ans;

    return 0;
}