[백준 알고리즘/C++/DP] 9465 스티커

 

 

한 스키커를 떼어내면 상하좌우의 스티커는 쓸 수 없게 된다

스티커에 점수를 매기고 점수의 합이 최대한 크도록 스티커를 사용하려고 할 때

점수의 최댓값을 출력하는 문제

 

 

전형적인 DP 문제다

 

멋진 그림

 

스티커의 행이 2로 고정되어 있으니 대각선으로 -1, -2만 보면 됨

i=2, arr[0][i] + max(arr[1][i-1], arr[1][i-2]) / arr[1][i] + max(arr[0][i-1], arr[0][i-2])가 된다!!

두칸을 뛰어넘는 경우는 없으므로 다른 경우의 수는 없음

합을 누적시켜야 하므로 dp배열을 사용해서 코딩하면 된다

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t, n;
    
    cin >> t;
    while (t--) {
        int arr[2][100001] = { 0, };
        int dp[2][100001] = { 0, };
 
        cin >> n;
        for (int i = 0; i < 2; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> arr[i][j];
            }
        }
 
        dp[0][1] = arr[0][1];
        dp[1][1] = arr[1][1];
 
        for (int i = 2; i <= n; i++) {
            dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + arr[0][i];
            dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + arr[1][i];
        }
 
        cout << max(dp[0][n], dp[1][n]) << "\n";
    }
}