[백준] 9465번 : 스티커

문제

 

---

풀이

 

문제의 조건에 따르면 스티커를 뗼 수 있는 방법은

 

OXOX  XOXO

XOXO  OXOX

 

이렇게 지그재그로 떼는 방법밖에 없다.

 

XXOX

XXXX

 

만약 이 동그라미로 표시한 스티커를 떼고 싶다고 하자. 그럼 그 이전까지의 스티커는 어떤 상태여야 할까?

 

OXOX  XXOX

XOXX  OXXX

 

이런 모습이어야 할 것이다.

그니까 연속으로 떼거나, 한 칸 건너뛰고 떼거나의 방법이 있는 것이다.

 

점화식을 작성하면

dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + cost[0][i];
dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + cost[1][i];

이렇게 된다.

 

dp[0][i]와 dp[1][i]중 더 큰 값이 스티커 점수의 최댓값이다.

---

소스코드

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int dp[2][100001];
vector<vector<int>> cost;

int dpSticker(int n) {
    dp[0][1] = cost[0][1];
    dp[1][1] = cost[1][1];

    for (int i = 2; i <= n; i++) { //붙여서 떼거나, 건너뛰고 떼거나
        dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + cost[0][i];
        dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + cost[1][i];
    }
    return max(dp[0][n], dp[1][n]);
}

int main() {
    int T, n, input;

    cin >> T;
    for (int i = 0; i < T; i++) {
        cost.assign(2, vector<int>(0));
        cost[0].push_back(0);
        cost[1].push_back(0);
        cin >> n;
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < n; k++) {
                cin >> input;
                cost[j].push_back(input);
            }
        }
        cout << dpSticker(n) << '\n';
        cost.clear();
    }
}