[C++ / 백준 9465번] 스티커

'

 

 

DP로 나누어 푸는 문제. 연상이 아직도 잘 안 된다.

 

경우의 수를 나누어서 풀었다.

 

 

 

#include <iostream>

using namespace std;

#define MOD 10007

int a[3][100001];
int dp[3][100001];

int main() {
    int N;

    cin >> N;

    for (int i = 0; i < N; i++)
    {

        int input;
        cin >> input;

        for (int k = 1; k <= 2; k++)
        {
            for (int j = 1; j <= input; j++)
            {
                int tmp;
                cin >> tmp;
                a[k][j] = tmp;
            }
        }

        dp[1][1] = a[1][1];
        dp[2][1] = a[2][1];

        dp[1][2] = a[1][2] + a[2][1];
        dp[2][2] = a[2][2] + a[1][1];


        for (int b = 3; b <= input; b++)
        {
            dp[1][b] = a[1][b] + max(dp[2][b - 2] , dp[2][b - 1] );
            dp[2][b] = a[2][b] + max(dp[1][b - 2] , dp[1][b - 1] );

        }

        cout << max(dp[1][input], dp[2][input]) << endl;



    }



    return 0;
}