[#9465] 스티커

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
 
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;
 
        vector<vector<int>> sticker(3, vector<int>(n + 1, 0));
        vector<vector<int>> dp(3, vector<int>(n + 1, 0));
        //dp[i][j]: j열의 i행을 떼어냈을 때 최대값. i==0 일 경우, j번째 열은 안떼어내는 것임
 
        for (int i = 1; i <= 2; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> sticker[i][j];
            }
        }
 
        dp[0][1] = 0;
        dp[1][1] = sticker[1][1];
        dp[2][1] = sticker[2][1];
 
        for (int i = 2; i <= n; i++) {
            dp[1][i] = max(dp[1][i - 2], max(dp[2][i - 2], dp[2][i - 1])) + sticker[1][i];
            dp[2][i] = max(dp[1][i - 2], max(dp[2][i - 2], dp[1][i - 1])) + sticker[2][i];
            dp[0][i] = max(dp[0][i - 1], max(dp[1][i - 1], dp[2][i - 1]));
        }
        cout << max(dp[0][n], max(dp[1][n], dp[2][n])) << "\n";
    }
    return 0;
}

나중에 생각해보니까 dp[i][j] 구할때 전전열 같은 행에서 오는 dp는 비교 안해줘도 됐었다.

왜냐면 전전열 같은 행에서 바로 오는것보다 전전열 같은 행 -> 전열 다른 행 -> 현재열 같은 행으로 오는게 무조건 더 크기 때문에 이미 전열 다른 행 비교할 때 비교 되어 있었을 것임