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

 
#include <iostream>
 
int sticker[2][100001] = {};
int dp[2][100001] = {};
 
int main()
{
    int T = 0;
    std::cin >> T;
 
    for (int i = 0; i < T; ++i)
    {
        int N = 0;
        std::cin >> N;
 
        for (int j = 0; j < N; ++j)
        {
            std::cin >> sticker[0][j];
        }
 
        for (int j = 0; j < N; ++j)
        {
            std::cin >> sticker[1][j];
        }
 
        dp[0][0] = sticker[0][0];
        dp[1][0] = sticker[1][0];
        dp[0][1] = sticker[0][1] + dp[1][0];
        dp[1][1] = sticker[1][1] + dp[0][0];
 
        for (int j = 2; j < N; ++j)
        {
            dp[0][j] = sticker[0][j] + std::max(dp[1][j - 1], dp[1][j - 2]);
            dp[1][j] = sticker[1][j] + std::max(dp[0][j - 1], dp[0][j - 2]);
        }
 
        std::cout << std::max(dp[0][N - 1], dp[1][N - 1]) << std::endl;
    }
 
    return 0;
}

 

1. dp는 한 개 차이의 대각선 or 두 개 차이의 대각선의 크기 중 큰 것으로 계산한다.

2. 마지막까지 이동했을 DP의 두개의 값 중 큰값을 제공한다.