BOJ 9465 스티커

boj 9465 스티커

위 그림과 같이, 문제의 조건에 따라 변을 공유하는 스티커는 뗄 수 없고, 대각으로만 이동하며 뗄 수 있다. 이 때, 대각으로 이동할 수 있는 경우는 아래 그림과 2가지가 있다. 3칸부터는 이동하면 중간에 거쳐갈 수 있는 칸이 무조건 있으므로 가장 높은 점수를 구하는 문제 조건에 어긋나므로 제외한다.

맨 위 그림을 보면, 스티커를 떼는 경로는 마지막에 떼지는 스티커가 첫번째 줄이냐 두번째 줄이냐로 나눠진다. 테이블 D[i][j]는 j번째 줄의 i번째 칸까지 스티커 점수의 최댓값으로 정의하고, score는 스티커의 점수를 담는 배열이다. 그러면 위의 내용을 점화식으로 정의해보자.

D[i][0] = max(D[i-1][1], D[i-2][1]) + score[i][0]
D[i][1] = max(D[i-1][0], D[i-2][0]) + score[i][1]

대각으로 이동할 때, 1칸 혹은 2칸 이동할 수 있으므로 그 두 경우를 비교해준 것이다. 이를 바탕으로 코드를 구현한다.

#include <iostream>
#include <algorithm>
using namespace std;

int t;
int n;
int D[100005][5];
int score[100005][5];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> n;
        for (int j = 0; j < 2; j++)
        {
            for (int k = 1; k <= n; k++)
            {
                cin >> score[k][j];
            }
        }

        D[1][0] = score[1][0];
        D[1][1] = score[1][1];

        for (int m = 2; m <= n; m++)
        {
            D[m][0] = max(D[m - 1][1], D[m - 2][1]) + score[m][0];
            D[m][1] = max(D[m - 1][0], D[m - 2][0]) + score[m][1];
        }

        cout << max(D[n][0], D[n][1]) << '\n';
    }
}