[백준 9465번] 스티커

소스코드

---

#include <iostream>
using namespace std;
 
int Max(int a, int b) {
    return a > b ? a : b;
}
 
int main() {
    int tc;
    cin >> tc;
    while (tc > 0) {
        int n,num[2][100001],dp[2][100001];
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> num[0][i];
        for (int i = 0; i < n; i++)
            cin >> num[1][i];
 
        dp[0][0] = num[0][0];
        dp[1][0] = num[1][0];
 
        dp[0][1] = num[1][0] + num[0][1];
        dp[1][1] = num[0][0] + num[1][1];
 
        dp[0][2] = Max(num[0][2] + num[1][1] + num[0][0], num[0][2] + num[1][0]);
        dp[1][2] = Max(num[1][2] + num[0][1] + num[1][0], num[1][2] + num[0][0]);
 
        for (int i = 3; i < n; i++) {
            int a = Max(num[0][i] + dp[1][i-1], num[0][i] + num[1][i-1] + dp[0][i-3]);
            int b = Max(num[1][i] + dp[0][i-1], num[1][i] + num[0][i-1] + dp[1][i-3]);
            dp[0][i] = Max(a, num[0][i] + dp[1][i-2]);
            dp[1][i] = Max(b, num[1][i] + dp[0][i-2]);
        }
        cout << Max(dp[0][n - 1], dp[1][n - 1]) << '\n';
        tc--;
    }
    return 0;
}