[C++] 백준 - 9465 : 스티커

문제 링크

9465번: 스티커

 

풀이 ) DP

  스티커를 윗줄과 아랫줄 2줄에서 떼어낼 수 있으므로 memo 배열을 1차원 배열 2개로 구성했다.

  윗줄의 스티커를 떼어내기 위해서는 왼쪽 아래칸을 떼거나 아예 안떼는 경우가 있다.

  아랫줄의 스티커를 떼어내기 위해서는 왼쪽 윗칸을 떼거나 아예 안 떼는 경우가 있다.

 

  윗줄을 memo[n][0], 아랫줄을 memo[n][1],

  전전 칸(떼지 않은 경우)까지의 최댓값 tmp = max(memo[n-2][0], memo[n-2][1])라 할 때,

  memo[n][0] = max(tmp, memo[n-1][1]) + arr[n][0], memo[n][1] = max(tmp, memo[n-1][0]) + arr[n][1]이 되고

  답은 이중 최댓값인 max(memo[n][0], memo[n][1])이다.

 

#include <cstdio>
#include <algorithm>
using namespace std;

int arr[100002][2], memo[100002][2];

int main(void)
{
    int t;
    scanf("%d", &t);
    while(t--){
        int n;
        scanf("%d", &n);
        for(int i = 0; i < 2; ++i)
            for(int j = 0; j < n; ++j)
                scanf("%d", &arr[j][i]);

        memo[0][0] = arr[0][0];
        memo[0][1] = arr[0][1];
        memo[1][0] = arr[0][1] + arr[1][0];
        memo[1][1] = arr[0][0] + arr[1][1];
        for(int i = 2; i < n; ++i){
            int tmp = max(memo[i-2][0], memo[i-2][1]);
            memo[i][0] = max(tmp, memo[i-1][1]) + arr[i][0];
            memo[i][1] = max(tmp, memo[i-1][0]) + arr[i][1];
        }
        printf("%d\n", max(memo[n-1][0], memo[n-1][1]));
    }
    return 0;
}