문제

풀이

2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

아래와 같은 형태로 점수가 정해진 상태로 스티커가 붙어 있다. 이때, (50,50,100,60)인 스티커를 떼면 총합이 260으로 변을 공유하지 않고 최대값을 가지는 부분집합이 된다.

dp[n][m] = n번째 열에서 스티커를 m했을 때, 2 x n 개의 스티커에서 얻을 수 있는 최대 점수
m = 0(위쪽 스티커) m = 1 (아래쪽 스티커) m = 2(둘다 뜯지 않음)

dp[n][0] = n번째 열에서 위쪽 스티커를 뜯어 얻은 최대 점수
dp[n][1] = n번째 열에서 아래쪽 스티커를 뜯어 얻은 최대 점수
dp[n][2] = n번째 열에서 둘다 뜯지 않고 얻은 최대점수

  1. n = 1 인 경우
    50
    30

dp[1][0] = 0
dp[1][1] = 50
dp[1][2] = 30

50을 선택하는 경우가 최대값을 가진다.

  1. n = 2 인 경우
    50 10 
    30 50

(50,50), (30,10), (50) 중 최대값을 가지는 (50,50)이 정답이다. 이를 수식으로 표현하면 아래와 같다.

dp[2][0] = max(dp[1][1], dp[1][2],dp[1][0]) = 50
dp[2][1] = dp[1][2] + a[2][1] = 40
dp[2][2] = dp[1][1] + a[2][2] = 100

  1. n = 3인 경우
    50 10 100
    30 50 70

dp[3][0] = max(dp[2][1],dp[2][2],dp[2][0]) = 100
dp[3][1] = dp[2][2] + a[3][1] = 200
dp[3][2] = dp[2][1] + a[3][2] = 110

  1. n = 4인 경우

    50 10 100 20
    30 50 70 10

    dp[4][0] = max(dp[3][1],dp[3][2],dp[3][0]) = 200
    dp[4][1] = dp[3][1] + a[4][2] = 210
    dp[4][2] = dp[3][2] + a[4][1] = 130

  2. n = 5 인 경우

    50 10 100 20 40
    30 50 70  10 60

    dp[5][0] = 210
    dp[5][1] = 260
    dp[5][2] = 240

코드


#include<cstdio>
#include<algorithm>
using namespace std;
int a[100001][3];
int dp[100001][3];
int n;
void solve() {

    dp[1][0] = a[1][0];
    dp[1][1] = a[1][1];
    dp[1][2] = 0;
    for(int i = 2; i <= n; i++) {
        dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + a[i][0];
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + a[i][1];
        dp[i][2] = max(max(dp[i-1][0], dp[i-1][1]), dp[i-1][2]);
    }
    printf("%d\n",max(max(dp[n][0],dp[n][1]), dp[n][2]));
}
int main() {
    int t;
    scanf("%d",&t);

    while(t--) {
        scanf("%d",&n);
        for(int i = 0; i < 2; i++) {
            for(int j = 1; j <= n; j++) {
                scanf("%d",&a[j][i]);
            }
        }
        solve();
    }

    return 0;
}