백준 9465번 스티커

https://www.acmicpc.net/problem/9465

이 문제를 풀기위해선 무작정 큰 스티커만을 찾아서 선택하는 로직을 사용해선 안된다.

 

100	99
99	1

만약 큰 스티커만 찾는다면 100을 찾을텐데, 이 문제의 답은 99 + 99 = 198 이기 때문이다.

풀이

1. N번째 열에서 택할 수 있는 가짓수는 3가지 이다.

   0 - 아무 스티커도 선택하지 않음( dp[N][0] )

   1 - 위에 스티커를 선택 ( dp[N][1] )

   2 - 아래 스티커를 선택 ( dp[N][2] )

   

  

2. 그렇다면 N번째 열에서 최대 값은 N-1 번째 열에서 각 가짓수에 의해 결정된다.

    N번째 행에서 아무 스티커도 선택하지 않았을 땐

    - N-1 번째 행에서 아무 스티커도 선택하지 않았을 때

    - N-1 번째 행에서 위에 스티커를 선택했을 때

    - N-1 번째 행에서 아래 스티커를 선택했을 때

   위의 3가지 경우에 대해 최대값을 선택하면 된다.

   

    N번째 행에서 위에 스티커를 선택했을 땐,

    - N-1 번째 행에서 아무 스티커도 선택하지 않았을 때

    - N-1 번째 행에서 위에 스티커를 선택했을 때

    - N-1 번째 행에서 아래 스티커를 선택했을 때

   위의 2가지 경우의 최대값과 N번째 행에서 윗 칸의 스티커 값을 더하면 된다.

    N번째 행에서 아래 스티커를 선택했을 땐,

    - N-1 번째 행에서 아무 스티커도 선택하지 않았을 때

    - N-1 번째 행에서 위에 스티커를 선택했을 때

    - N-1 번째 행에서 아래 스티커를 선택했을 때

   위의 2가지 경우의 최대값과 N번째 행에서 아래칸의 스티커 값을 더하면 된다.

#include <iostream>
#define MAX 100000
using namespace std;
int main()
{
    int T, n;
    
    scanf("%d\n", &T);
    for(int i = 0; i < T; ++i) {
        scanf("%d", &n);
        
        int s[2][MAX + 1] = {0, };
        for (int x = 0; x < 2; ++x) {
            for (int y = 0; y < n; ++y) {
                scanf("%d", &s[x][y]);
            }
        }
        // 0 : 위, 아래 모두 안뜯음
        // 1 : 위에 스티커 선택
        // 2 : 아래 스티커 선택
        // 위, 아래 둘다는 선택하지 못함
        int dp[MAX + 1][3] = {0, };
        dp[0][0] = 0;
        dp[0][1] = s[0][0];
        dp[0][2] = s[1][0];
        for (int m = 1; m < n; ++m) {
            dp[m][0] = max(dp[m-1][2], max(dp[m-1][0], dp[m-1][1]));
            dp[m][1] = max(dp[m-1][0], dp[m-1][2]) + s[0][m];
            dp[m][2] = max(dp[m-1][0], dp[m-1][1]) + s[1][m];
        }
        
        printf("%d\n", max(dp[n-1][2], max(dp[n-1][0], dp[n-1][1])));
    }
    return 0;
}