9465번 스티커

문제 링크

스티커

문제 풀이

스티커를 선택하면 인접한 스티커는 사용하지 못한다. 그렇기에 위, 아래, 선택안하는 3가지의 경우가 생긴다. 만약 그 전 열에서 위 스티커를 선택했으면 아래와 선택안하는 경우 2가지만 선택할 수 있고, 아래 스티커를 선택했으면 2가지, 선택안했으면 3가지의 경우가 생긴다. 따라서 이전에 선택한 스티커의 상태를 알아야 하므로 점화식의 변수는 2개가 된다. 다음은 이를 바탕으로 점화식은 세운 것이다.

구현

#include <iostream> 
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

int TC, N;
int sticker[2][100001];
int cache[3][100001];

// caseNum : 그 전에 0 = 위칸선택, 1 = 아래칸선택, 2 = 선택안함
int solve(int n, int caseNum) {
    if (n == N) return 0;

    int& ret = cache[caseNum][n];
    if (ret != -1) return ret;

    ret = solve(n + 1, 2);
    if (caseNum == 0) 
        ret = max(ret, solve(n + 1, 1) + sticker[0][n]);
    else if (caseNum == 1) 
        ret = max(ret, solve(n + 1, 0) + sticker[1][n]);
    else {
        ret = max(ret, solve(n + 1, 1) + sticker[0][n]);
        ret = max(ret, solve(n + 1, 0) + sticker[1][n]);
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> TC;
    while (TC--) {
        cin >> N;
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < N; ++j)
                cin >> sticker[i][j];
        memset(cache, -1, sizeof(cache));
        cout << solve(0, 2) << endl;
    }
    return 0;
}