[백준/C++] 9465번: 스티커

풀이

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin.tie(NULL);

    int T;
    cin >> T;

    while(T--) {
        int n;
        cin >> n;

        int sticker_value[2][n];

        for( int i = 0; i < 2; ++i ) {
            for( int j = 0; j < n; ++j ) cin >> sticker_value[i][j];
        }

        for( int i = 1; i < n; ++i ) {
            if( i == 1 ) {
                sticker_value[0][i] += sticker_value[1][i - 1];
                sticker_value[1][i] += sticker_value[0][i - 1];
            } else {
                sticker_value[0][i] += max(sticker_value[1][i - 1], sticker_value[1][i - 2]);
                sticker_value[1][i] += max(sticker_value[0][i - 1], sticker_value[0][i - 2]);
            }
        }

        cout << max(sticker_value[0][n - 1], sticker_value[1][n - 1]) << '\n';

    }

    return 0;
}

1) 스티커를 2n개 구매하므로, 각 스티커에 저장된 점수를 sticker_value라는 2차원 배열의 형태로 저장
2) 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 시작 부분을 고려하면, [0][1] 위치의 스티커를 떼면 [1][0] 위치의 스티커를 뗄 수밖에 없고, [1][1] 위치의 스티커를 떼면 [0][0]dml 스티커를 뗄 수밖에 없다.
3) 이후에는 max함수를 사용해서 i번째 위치의 값에 다른 행의 i-1번째 위치, i-2번째 위치(why?)의 값중 더 큰 것을 더하고 가장 큰 값을 출력한다.
-> i - 1 번째 위치와 i - 2번째 위치를 비교하는 이유는 스티커를 떼면 양 옆으로 1칸씩 사용할 수 없기에 i - 3번째 위치를 고려하면 그 전에 다른 sticker를 뗄 수 있어 최댓값을 만들 수 있기 때문에 모순