[B9465] - 스티커

https://www.acmicpc.net/problem/9465 스티커입니다. 스티커를 최대한의 점수를 갖게 떼어내는 방법을 구하는 것이 목표입니다.

최종답을 구할 때 이전 상태를 이용해야하기 때문에 dp로 풀 수 있습니다.

어떤 위쪽 칸에 들어가는 최대값을 구하고 싶다면  그 전전칸의 위쪽의 최대값+전 칸의 아래쪽 값과 그 전 칸의 아래쪽 값 중 큰 값에 a[i][0]을 더해주면 됩니다.

d[i][0]=max(d[i-2][0]+a[i-1][1],d[i][1])+a[i][0]으로 표현할 수 있네요

그런데 이 값보다 전칸의 위쪽값이 더 크다면 어떨까요?

즉 a[i][0]의 스티커를 떼어내지 않는 경우도 있을 수 있습니다.

그러므로 d[i][0]=max(d[i-1][0],max(d[i-2][0]+a[i-1][1],d[i][1])+a[i][0]) 이 되겠군요

아래쪽도 마찬가지로 식을 세우면 되겠습니다.

#include <iostream>
using namespace std;
int a[100001][2] = { 0, };
int d[100001][2] = { 0, };
int max(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}
int main()
{
    int T;
    cin >> T;
    for (int test_case = 1; test_case <= T; ++test_case)
    {
        int n;
        cin >> n;
 
        for (int i = 0; i < n; i++)
        {
            cin >> a[i][0];
            d[i][0] = 0;
            d[i][1] = 0;
        }
        for (int i = 0; i < n; i++)
        {
            cin >> a[i][1];
        }
        d[0][0] = a[0][0];
        d[0][1] = a[0][1];
        d[1][0] = max(a[1][0] + a[0][1], a[0][0]);
        d[1][1] = max(a[0][0] + a[1][1], a[0][1]);
        for (int i = 0; i + 2 < n; i++)
        {
            d[i + 2][0] = max(d[i + 1][0], max(d[i][0] + a[i + 1][1], d[i][1]) + a[i + 2][0]);
            d[i + 2][1] = max(d[i + 1][1], max(d[i][1] + a[i + 1][0], d[i][0]) + a[i + 2][1]);
        }
        int ans = max(d[n - 1][1], d[n - 1][0]);
        cout << ans << '\n';
    }
}