백준 #9465 스티커


BOJ #9465 - 스티커

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

# 문제 분류

Dynamic Programming

풀이 접근 방법


  1. 2행짜리 배열을 요리조리 왔다갔다하면서 최댓값이 결정된다는 것이 좀 골치아파 보이는 문제이다.
  2. 하나를 제거하면 마주보는 변의 스티커는 제거할 수 없기 때문에, 대각선 방향으로 보는 것으로 생각하면 된다.
  3. DP 배열을 3행으로 만들어서, 1, 2행은 각각의 스티커를 제거했을 때의 dp값을, 3행은 제거하지 않았을 때의 dp값을 저장.

Line 32에서 i == j 일 때 continue 해준 것이 바로 마주보는 변의 스티커를 동시에 제거할 수 없음을 말하는 것이다.
점화식은 dp[i][j] = max(dp[i+1][j-1], dp[i-1][j-1])

소스 코드


#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <vector>

using namespace std;

int T, n;
int INF = 1e9;


int main(){
    scanf("%d", &T);

    for(int i=0; i<T; i++){
        int arr[4][100010] = {0};
        int dp[4][100010] = {0};
        scanf("%d", &n);

        for(int j=1; j<3; j++){
            for(int k=1; k<n+1; k++){
                scanf(" %d", &arr[j][k]);
            }
        }

        for(int k=1; k<n+1; k++){
            for(int j=1; j<=3; j++){
                int maxx = 0;
                for(int l=1; l<=3; l++){
                    if(l==j) continue;
                    maxx = max(maxx, dp[l][k-1]);
                }
                dp[j][k] = maxx + arr[j][k];
            }
        }

        int res = 0;
        for(int k=1; k<=3; k++){
            res = max(res, dp[k][n]);
        }

        printf("%d\n", res);
    }

    return 0;
}