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

문제 - 연속합2 (Gold5)

[백준 13398] https://www.acmicpc.net/problem/13398

풀이 전략

2차원 DP배열을 만들어서 첫 번째 행은 숫자를 제거하지 않는 경우, 두 번째 행은 숫자 1개를 제거한 경우를 나누어서 마지막에 두 행을 비교해서 더 큰 값이 구해지는 행을 출력하는 방식을 썼다.

풀이

소스 코드

/*문제 : https://www.acmicpc.net/problem/13398
  알고리즘 : DP
  티어 : Gold5
*/
#include <iostream>
#include <vector>
#define MAX 100001
using namespace std;

int N;
int DP[MAX][2];
int arr[MAX];

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N;

    for(int i=0;i<N;i++){
        cin>>arr[i];
    }
    DP[0][0]=arr[0];
    DP[0][1]=arr[0];
    int result=arr[0];

    for(int i=1;i<N;i++){
        DP[i][0]=max(DP[i-1][0]+arr[i],arr[i]);
        DP[i][1]=max(DP[i-1][0],DP[i-1][1]+arr[i]);
        result=max(result,max(DP[i][0],DP[i][1]));
    }
    
    /*
    DP배열의 값을 출력하기 위한 Code
    for(int i=0;i<N;i++){
        cout<<DP[i][0]<<" ";
    }
    cout<<'\n';
    for(int i=0;i<N;i++){
        cout<<DP[i][1]<<" ";
    }
    cout<<'\n';
    */
    
    cout<<result<<'\n';
    return 0;
}

결과

문제

문제 (DP 출력 포함)

또 다른 예시 (DP 출력 포함)