DP_백준_스티커_9465

순서가 정해져 있지 않다는것은 우리가 스티커를 때는 순서를 정할 수 있다. 즉 왼쪽부터 한 열씩 스티커를 어떻게 뜯을지를 결정한다. 이 문제 또한 길이가 N 일때 마지막 상태가 정해져 있지 않아서 2차원 배열로 마지막 상태를 표현한다.

1. 정의 : dp[N][M] : 2*N에서 얻을 수 있는 최대점수, M=0(뜯지 않음), M=1(위쪽 스티커를 뜯음), M=2(아래쪽 스티커를 뜯음)

2. 점화식 : dp[N][0] = max(dp[N-1][0], dp[N-1][1], dp[N-1][2])

              dp[N][1] = max(dp[N-1][0], dp{n-1][2]) + value[0][N]

              dp[N][2] = max(dp[N-1][0], dp[N-1][1]) +value[1][N]

3. 초기화 : 코드참조

#include <iostream>
using namespace std;
 
int max(int a, int b, int c) {
    int tmp = a;
    if (tmp < b)
        tmp = b;
    if (tmp < c)
        tmp = c;
    return tmp;
}
 
int main() {
    int count;
    cin >> count;
    for (int q = 0; q < count; q++) {
        int num; // N Length
        cin >> num;
 
        int ** value = new int*[2]; //Input
        int ** dp = new int*[num]; // DP memoization
 
        for (int i = 0; i < 2; i++) {
            value[i] = new int[num];
        }
        for (int i = 0; i < num; i++) {
            dp[i] = new int[3];
        }
        //Create
 
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < num; j++) {
                cin >> value[i][j];
            }
        }
            // Input
 
        dp[0][0] = 0;
        dp[0][1] = value[0][0];
        dp[0][2] = value[1][0];
        //Initialize
 
        for (int i = 1; i < num; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] = max(dp[i - 1][0], dp[i - 1][2], 0) + value[0][i];
            dp[i][2] = max(dp[i - 1][0], dp[i - 1][1], 0) + value[1][i];
        }
        //Calculate
        cout << max(dp[num - 1][0], dp[num - 1][1], dp[num - 1][2]) << endl;
    }
    return 0;
}