[백준][9465] 스티커

문제

제약 확인

총 스티커의 수가 2N 개일 때 N 의 범위가 \(1 <= N <= 100,000\) 이므로 최대 200,000 개가 입력될 수 있습니다.
따라서 시간 복잡도가 \(O(N)\) 이하의 알고리즘을 사용해야 합니다.

알고리즘 선택

스티커를 선택할 때, 각 선택은 작은 문제로 나누어 접근할 수 있습니다.
즉, a번 열까지의 결과는 1번부터 a번 열까지의 최댓값으로 계산할 수 있습니다.

풀이 코드

int T, N, temp;
vector<int> sticker[2];

void input() {
    cin >> N;
    for (int row = 0; row < 2; ++row) {
        sticker[row].assign(N + 2, 0);
        for (int col = 2; col <= N + 1; ++col) {
            cin >> temp;
            sticker[row][col] = temp;
        }
    }
}

void solve() {
    for(int curr = 2; curr <= N + 1; ++curr) {
        sticker[0][curr] += max(sticker[1][curr - 1], sticker[1][curr - 2]);
        sticker[1][curr] += max(sticker[0][curr - 1], sticker[0][curr - 2]);
    }
    printf("%d\n", max(sticker[0][N + 1], sticker[1][N + 1]));
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    cin >> T;
    while(T--) {
        input();
        solve();
    }
    return 0;
}

문제의 설명에서 한 스티커를 선택하면 그 스티커의 변을 공유하는 다른 스티커는 사용할 수 없게 됩니다.
따라서 현재 선택된 스티커의 왼쪽, 오른쪽, 위, 아래는 선택될 일이 없습니다.