[C++] BOJ 9465번: 스티커

문제 링크

문제 풀이

dp를 이용하여 해당 칸의 스티커가 선택되었을 경우의 최고 점수, 선택되지 않았을 때의 최고 점수를 계산하여 문제를 해결하였다. dp1은 상단 부분의 n열 스티커를 고른 경우, dp2는 하단 부분의 n열 스티커를 고른 경우, dp3는 n열의 스티커를 아무것도 고르지 않은 경우의 최고 점수이다.

 

코드를 보면 max를 많이 사용하였는데 이는 최고 점수를 구하기 위해 비교해야 할 대상이 많았기 때문이다.

코드

#include <bits/stdc++.h>

using namespace std;

int T;
int n;

int stickerScore[100003][3];
int result;

int dp1[100003]; // 위에 쪽 선택했을 때
int dp2[100003]; // 아래 쪽 선택했을 때
int dp3[100003]; // 아무 것도 선택 안했을 때

void calcDp(int depth)
{
    if (depth > n)
        return;
    if (depth == 1)
    {
        dp1[1] = stickerScore[1][1];
        dp2[1] = stickerScore[1][2];
        dp3[1] = 0;
    }
    else if (depth == 2)
    {
        dp1[2] = stickerScore[1][2] + stickerScore[2][1];
        dp2[2] = stickerScore[1][1] + stickerScore[2][2];
        dp3[2] = max(dp1[1], dp2[1]);
    }
    else
    {
        dp1[depth] = max(max(max(dp1[depth - 1], dp1[depth - 2] + stickerScore[depth][1]), dp2[depth - 1] + stickerScore[depth][1]), dp3[depth - 1] + stickerScore[depth][1]);
        dp2[depth] = max(max(max(dp2[depth - 1], dp2[depth - 2] + stickerScore[depth][2]), dp1[depth - 1] + stickerScore[depth][2]), dp3[depth - 1] + stickerScore[depth][2]);
        dp3[depth] = max(dp1[depth - 1], dp2[depth - 1]);
    }
    calcDp(depth + 1);
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;

    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= 2; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                cin >> stickerScore[j][i];
            }
        }
        calcDp(1);

        result = max(max(dp1[n], dp2[n]), dp3[n]);

        cout << result << '\n';
    }

    return 0;
}