[백준][9465번][DP] 스티커

스티커
https://www.acmicpc.net/problem/9465

<코드>

#include <stdio.h>
 
int stiker[2][100010];
int dp[2][100010];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
int main(void){
 
    int testcase;
    scanf("%d", &testcase);
    while (testcase--){
        int n;
        
        scanf("%d", &n);
 
        for (int i = 0; i < 2; i++)
            for (int j = 2; j <= n+1; j++)
                scanf("%d", &stiker[i][j]);
 
 
        for (int i = 2; i <= n+1; i++){
                dp[0][i] = max(max(dp[0][i - 1], dp[1][i - 1] + stiker[0][i]), dp[1][i - 2] + stiker[0][i]);
                dp[1][i] = max(max(dp[1][i - 1], dp[0][i - 1] + stiker[1][i]), dp[0][i - 2] + stiker[1][i]);
        }
 
 
        if (dp[0][n+1] > dp[1][n+1])
            printf("%d\n", dp[0][n+1]);
        else
            printf("%d\n", dp[1][n+1]);
    }
 
    return 0;
}

<문제 푼 요령>

1. 이 문제는 현재의 쭈욱 검색해 나가면서 스티커를 붙일경우와 붙이지 않을경우의 최대값을 비교해주면 된다. 

2. 각 포인트를 비교해줘야 할 요소는 3가지이다. 그 요소는 아래 그림과 같다. 즉 스티커를 선택 안했을 경우는 이전의 값과 스티커를 선택했을 때 대각선의 값 그리고 마지막으로 스티커를 선택 할 경우 이전 이전의 대각선 값을 비교해야 한다. 

3. 2번에서 비교한 값중 최대값을 넣어준다. 이 방식을 반복하면서 채워나가면 마지막에 채워진 값중에서 최대값이 최대 스티커 값이 되는 것이다.