백준 9465. 스티커

다시 푼 문제.

www.acmicpc.net/problem/9465

9465번: 스티커

이전 글 : tose33.tistory.com/17

 

d[n] : 2 x n 의 스티커에서 점수의 합이 최대가 되는 점수.

 

그런데 스티커를 때어내면 위,아래,좌,우 의 스티커는 못쓰게된다. 

따라서 n번째 스티커를 때어낼때 케이스를 나눠 생각한다.

 

d[n][0] : n번째에 스티커를 안때어냄

d[n][1] : n번쨰에서 위쪽의 스티커를 때어냄.

d[n][2] : n번째에서 아랫쪽의 스티커를 때어냄.

 

 

1. d[n][0] : n번째에 스티커를 안때어냄

이 경우 이전 n-1번째에서 아래 스티커를 때든, 위 스티커를 때든, 스티커를 안때든 상관이없다. 따라서

d[n][0] = max(d[n-1][0], d[n-1][1], d[n-1][2])

 

2. d[n][1] : n번쨰에서 위쪽의 스티커를 때어냄.

이 경우 n번째에서 위쪽의 스티커를 때어내려면, n-1번째에서 스티커를 안때거나, 아랫쪽의 스티커를 때어냈어야 한다. 따라서

n-1번째에서 아랫쪽을 때어냈을때의 최대점수 d[n-1][2] 와 n-1번째 에서 안때어냈을 때의 최대 점수 d[n-1][0]중 큰 값에

n번째 에서 위의 점수인 score[0][n]을 더한값이다.

d[n][1] = max(d[n-1][0], d[n-1][2]) + score[0][n]

 

3. d[n][2] : n번째에서 아랫쪽의 스티커를 때어냄.

이 경우 n번째에서 아랫쪽의 스티커를 때어내려면, n-1번째에서 스티커를 안때거나, 위쪽의 스티커를 때어냈어야 한다. 따라서

n-1번째에서 위쪽응ㄹ 때어냈을때의 최대점수인 d[n-1][1]과 n-1번째에서 안때어냈을 떄의 최대점수 d[n-1][0]중 큰 값에, 

n번째 에서 아래의 점수인 score[1][n]을 더한값이다.

d[n][2] = max(d[n-1][0], d[n-1][1]) + score[1][n] 

 

이렇게 bottom-up으로 데이터를 n번째 까지 쌓아간다. 

그리고 d[n][0], d[n][1], d[n][2] 중 가장 큰 값이 정답이다. 

 

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

int d[100001][3];
int score[2][100001];

int main() {
    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 >> score[i][j];
            }
        }

        d[1][0] = 0; // 안떄어냄
        d[1][1] = score[0][1]; // 위를 때어냄
        d[1][2] = score[1][1]; // 아래를 때어냄

        for(int i = 2; i <= n; i++) {
            d[i][0] = max({d[i-1][0], d[i-1][1], d[i-1][2]});
            d[i][1] = max(d[i-1][2], d[i-1][0]) + score[0][i];
            d[i][2] = max(d[i-1][1], d[i-1][0]) + score[1][i];
        }

        cout << max({d[n][0], d[n][1], d[n][2]}) << '\n';

    }
}