[C++] 백준 BOJ 9465 스티커

문제링크 : https://boj.kr/9465

DP 문제로 아래의 3가지 케이스로 계산할 수 있다.

case 1.

o x

x o

case 2.

o x x

x x o

case 3.

x x o x

o x x o

// BOJ 9465 스티커
#include <iostream>
#include <vector>
 
int max(int a, int b) {
    return a > b ? a : b;
}
int max(int a, int b, int c){
    return max(max(a, b), c);
}
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int tc;
    cin >> tc;
    while (tc--) {
        int num;
        cin >> num;
 
        vector<vector<int> > arr(3, vector<int>(num + 1, 0));
        vector<vector<int> > dp(3, vector<int>(num + 1, 0));
 
        for(int n = 1; n <= 2; n++)
            for (int i = 1; i <= num; i++)
                cin >> arr[n][i];
 
        dp[1][1] = arr[1][1];
        dp[2][1] = arr[2][1];
 
        for(int i = 3; i <= num; i++){
            dp[1][i] = max(dp[2][i-2], dp[1][i-2] + arr[2][i-1],
                dp[1][i-3] + arr[2][i-1]) + arr[1][i];
            dp[2][i] = max(dp[1][i-2], dp[2][i-2] + arr[1][i-1],
                dp[2][i-3] + arr[1][i-1]) + arr[2][i];
        }
 
        cout << max(dp[1][num], dp[2][num]) << '\n';
    }
 
    return 0;
}