BOJ : 9465 스티커

---

[BOJ 9465(S2) 리뷰]

DP문제다.

우리는 점수가 적인 2*N개의 스티커를 떼었을때 최대값이 되는 크기를 출력해야 한다.

다만 스티커를 뗄때는 다음과 같은 조건이 붙는다.

떼고자 하는 스티커와 변을 공유하는 스티커는 찢어지기에 다음번에 그 스티커는 뗄 수 없다.

50 30 20

20 10 30

이라는 스티커가 있을때 만약 50이라는 스티커를 떼게되면 오른쪽에 있는 30과 아래에 있는 20은 뗄 수 없다.

이러한 조건을 만족하며 스티커를 뗐을때의 최대값을 구하면 된다.

 

천천히 생각해 보자.

N이 1이라면

50

20 

당연히 두개의 스티커 중 더 큰 값을 떼어내야 한다.

 

N이 2라면

50 10

30 10

이 경우에는 50+10=60, 30+10=40 이므로 50과 10의 스티커를 떼어내야 한다.

 

이제 N이 3이상인 경우부터가 중요하다.

50 10 20

30 10 80

이 경우에는 어떻게 떼어야할까? 최대값은 130이다.

 

50 10 20

30 10 80

50과 80을 떼어내야만 가장 큰 값이 된다.

즉, 여기서 우리는 두번째 열에 있는 스티커떼는 과정을 생략해야 한다.

만약 10이라는 스티커를 떼어냈다면 80이라는 스티커를 떼어낼 수 없기 때문이다.

 

이러한 논리를 그대로 코드에 옮기면 된다.

예를들어 우리가 80이 위치한 스티커까지의 dp값을 계산할때

50 10 20

30 10 80 의 경우와

 

50 20 20

30 10 80

의 경우 중 더 큰 값을 dp배열에 담으면 된다.

 

 

나는 2차원 배열을 통해 dp값을 관리했다.

dp[0][2]는 두번째 열의 위쪽 스티커를 떼어냈을때 까지의 최대값을 담는다.

dp[1][3]은 세번 째 열의 아래쪽 스티커를 떼어냈을때 까지의 최대값을 담는다.

 

 

---

#include <bits/stdc++.h>
using namespace std;
 
int sticker[2][100001];
int dp[2][100001];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        int N;
        cin >> N;
        for (int i = 0; i < 2; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                cin >> sticker[i][j];
            }
        }

        dp[0][1] = sticker[0][1];
        dp[1][1] = sticker[1][1];
        dp[0][2] = sticker[1][1] + sticker[0][2];
        dp[1][2] = sticker[0][1] + sticker[1][2];

        int ans = 0;
        for (int i = 3; i <= N; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                int val = max(dp[0][i - 2], dp[1][i - 2]);
                dp[j][i] = max(val + sticker[j][i], dp[1 - j][i - 1] + sticker[j][i]);
                ans = max(ans, dp[j][i]);
            }
        }

        cout << ans<<'\n';
    }

    
}