[백준/c++] BOJ 9465 - 스티커

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

9465번: 스티커

 

문제 설명

스티커 2n개를 그림 (a)와 같이 2행 n열로 배치한다. 스티커의 품질이 매우 좋지 않아서 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 각 스티커에 점수를 매기고, 점수의 합이 최대가 되도록 스티커를 떼어내려고 한다. 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유하지 않는 스티커 집합 점수의 최댓값을 구한다.

 

해결

우리가 구하고자 하는 것을 명확히 해 보자.

- 2n개의 스티커 중 두 변을 공유하지 않고, 점수의 합이 최대로 되는 스티커 집합의 점수

 

dp[n] = n번째까지의 최대 점수

 

 

 

dp[0][0] = arr[0][0] or arr[1][0]

dp[1][0] = arr[0][0] or arr[1][0]

 

dp[0][1] = dp[1][0] + arr[0][1] || dp[0][0]

dp[1][1] = dp[0][0] + arr[1][1] || dp[1][0]

 

...

 

dp[0][n] = dp[0][n - 1] || dp[1][n-1] + arr[0][n]

dp[1][n] = dp[1][n - 1] || dp[0][n-1] + arr[1][n]

 

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
#define INF 1e9
using namespace std;

int n;
int arr[2][100001], m, dp[2][100001];

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

    cin >> n;
    while (n--) {
        cin >> m;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < m; j++)
                cin >> arr[i][j];
        }
        dp[0][0] = arr[0][0], dp[1][0] = arr[1][0];
        for (int i = 1; i < m; i++) {
            dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] + arr[0][i]);
            dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + arr[1][i]);
        }

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