[boj] 백준 9465 스티커 (c++) - dp

[문제]

https://www.acmicpc.net/problem/9465

9465번: 스티커

 

[풀이]

처음 bfs 문제인 줄 알고 엄청 헤맸다.....n ≤ 100,000 이라 dp로 해결할 수 있다.

 

첫번째 스티커를 뗀다고 생각해보자. 그 다음에 뗄 수 있는 스티커는 오른쪽과 아래의 10, 30을 제외한 스티커이다. 50을 뗀다면 그 다음은 100, 10, 60 처럼 위, 아래로 움직이며 스티커를 뗄 수 있을 것이다.

그렇다면 50만 뗄 수 있을까? 아니다!

50이 아니라 옆옆에 있는 100을 뗄 수도 있고, 50 옆에 있는 70을 뗄 수도 있다. 그런데 만약 100을 뗀다고 가정하면, 아래에 있는 50 역시 뗄 수 있으므로 처음과 같은 결과가 될 것이다. 

이를 고려해서 점화식을 짜면 다음과 같다.

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

 

[코드]

 

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>

using namespace::std;

int sticker[2][100001];
int dp[2][100001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    for(int i=0; i<t; i++){
        int n;
        cin >> n;

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

        dp[0][0] = sticker[0][0];
        dp[0][1] = sticker[0][1] + sticker[1][0];
        dp[1][0] = sticker[1][0];
        dp[1][1] = sticker[0][0] + sticker[1][1];

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

        cout << max(dp[0][n-1], dp[1][n-1]) << "\n";

    }

}