스티커 9465

문제

접근 방법

스티커를 최대로 사용하려면 위아래로 번갈아 가면서 가져가는 법이 있다. 하지만 최대의 점수를 보장하지는 않는다.

번갈아 가며 가져가면 10이라는 값밖에 못 얻지만 한 칸을 포기하고 다음 칸에서 가져간다면 20이라는 값을 가질 수 있다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
long long dp[2][100000];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        for (int j = 0; j < 2; ++j)
            for (int i = 0; i < n; ++i)
            {
                cin >> dp[j][i];
            }
        if (n > 1)
        {
            dp[0][1] += dp[1][0];
            dp[1][1] += dp[0][0];
        }
        for (int i = 2; i < n; ++i)
        {
            for (int j = 0; j < 2; ++j)
            {
                int k = (j + 1) % 2;
                dp[j][i] += max(dp[k][i - 1], dp[k][i - 2]);
            }
        }
        cout << max(dp[0][n - 1], dp[1][n - 1]) << "\n";
    }
    return 0;
}

풀이

개수보다는 최댓값에 초점을 두어야 한다.