9465 스티커

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

9465번: 스티커

---

접근

RGB문제와 유사한 문제여서 매우 쉽게 풀었다.

 

스티커를 떼면 상하좌우에 있는 스티커들은 쓸 수가 없다. 최대한 많은 가치의 스티커를 떼어보자는 거다.

 

왼쪽부터 스티커를 뜯는다고 생각하자. 직전에 어떻게 뜯었냐에 따라 다음 스티커의 운명이 정해진다.

 

직전에 아래쪽 스티커를 떼어냈다면 다음 열의 아래쪽 스티커는 뜯을 수 없다. 

따라서, 윗쪽 스티커를 떼어내기 또는 스티커를 떼지 않는 선택 두 가지밖에 없다.

 

직전에 윗쪽 스티커를 떼어냈다면 다음 열의 윗쪽 스티커는 뜯을 수 없다.

따라서, 아래쪽 스티커를 떼어내기 또는 스티커를 떼지 않는 선택 두 가지밖에 없다.

 

직전에 아무 스티커도 떼지 않았다면 다음 열의 어느 스티커든지 뜯을 수 있다.

따라서, 윗쪽 스티커를 떼어내기 또는 아래쪽의 스티커를 떼어내기 또는 아무 스티커도 떼지 않는 선택 세 가지밖에 없다.

 

가능한 행동이 3가지나 되므로 dp배열을 3행 n열로 만들어 각 행동에 대해 최대값을 누적시키면서 찾아나가면 된다.

---

#include <iostream>
#define MAX(X, Y) ((X) > (Y) ? (X) : (Y))
int main() {
  int T;
  scanf("%d", &T);
  for (int cases = 1; cases <= T; cases++) {
    int N, dp[3][100001]{0}, arr[2][100001]{0};
    scanf("%d", &N);

    for (int i = 0; i < 2; i++) {
      for (int j = 1; j <= N; j++) {
        scanf("%d", &arr[i][j]);
      }
    }

    for (int i = 1; i <= N; i++) {
      dp[0][i] = MAX(dp[1][i - 1], dp[2][i - 1]) + arr[0][i];
      dp[1][i] = MAX(dp[0][i - 1], dp[2][i - 1]) + +arr[1][i];
      dp[2][i] = MAX(dp[0][i - 1], MAX(dp[1][i - 1], dp[2][i - 1]));
    }
    printf("%d\n", MAX(dp[0][N], MAX(dp[1][N], dp[2][N])));
  }
}