13398번

13398번 - 연속합 2

고민하다가 결국 인터넷을 뒤적이며 점화식을 보고 문제를 풀었다.

인터넷에서 본 점화식에서는 n번째 원소를 선택한다 라는 설명이 없어서.. 처음에 많이 헤매다가 slack 에 물어보고 알아냈다.

일단 점화식은

D[n][0] = n번째 원소를 선택하고, 하나도 삭제하지 않고 얻은 수열의 최대값.

D[n][1] = n번째 원소를 선택하고, 하나를 삭제하고 얻은 수열의 최대값.

D[n][0] = max( D[n-1][0]+v[n-1] , v[n-1] )

D[n][1] = max( D[n-2][0]+v[n-1], D[n-1][1] + v[n-1]) 

라는 점화식으로 문제를 풀 수 있었다. 따라서 모든 D 배열을 비교해서 최대값을 찾아야 하낟.

##실수한 점

D에 음수가 들어갈 수 있을 때! D 초기화를 조심할 것.

항상 대부분 자연수 DP를 풀다보니, 습관적으로 코딩을 할때가 있는데, 조심해야 한다.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
int D[100001][2];
const int INF = -1000000001;
vector<int> v(100001);
int go(int n, int i)
{
    if (n <= 0)
    {
        return 0;
    }
    if (n == 1)
    {
        return v[0];
    }
 
    if (D[n][i] != INF)
    {
        return D[n][i];
    }
 
    if (D[n][i] == INF)
    {
        D[n][i] = 0;
    }
 
    if (i == 0)
    {
        D[n][i] = max(go(n - 1, 0) + v[n - 1], v[n - 1]);
    }
    if (i == 1)
    {
        D[n][i] = max(go(n - 2, 0) + v[n - 1], go(n - 1, 1) + v[n - 1]);
    }
 
    return D[n][i];
}
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
    {
        D[i][0] = INF;
        D[i][1] = INF;
    }
 
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &v[i]);
    }
    int ans = INF;
    for (int i = 1; i <= n; i++)
    {
        ans = max({ ans, go(i, 0), go(i, 1) });
    }
    printf("%d\n", ans);
 
    return 0;
}