[백준] 9465 - 스티커

dp문제 중에 무조건 풀어야하는 기초문제인 것 같습니다.

한 열에서 스티커를 선택하지 않을 경우, 첫번째 행의 스티커를 선택할 경우, 두번째 행의 스티커를 선택할 경우로 나누어

이전 열에서 가장 큰 값을 더해주는 식으로 dp를 풀어주면 N번 연산으로 끝낼 수 있습니다.

#include <iostream>
#define SIZE 100003
#define MAX(X, Y) ((X) > (Y) ? (X):(Y))
using namespace std;
 
int map[3][SIZE], dp[3][SIZE];
int T, N;
 
int main(void)
{
    cin >> T;
    while (T--)
    {
        cin >> N;
 
        for (int i = 1; i < 3; i++)
            for (int j = 1; j <= N; j++)
            {
                cin >> map[i][j];
                dp[i][j] = 0;
            }
        for (int i = 1; i <= N; i++)
        {
            dp[0][i] = MAX(dp[0][i - 1], MAX(dp[1][i - 1], dp[2][i - 1]));
            dp[1][i] = MAX(dp[0][i - 1], dp[2][i - 1]); dp[1][i] += map[1][i];
            dp[2][i] = MAX(dp[0][i - 1], dp[1][i - 1]);    dp[2][i] += map[2][i];
        }
        cout << MAX(dp[0][N], MAX(dp[1][N], dp[2][N])) << endl;
    }
    return 0;
}