스티커 백준 9465

문제

스티커 백준 9465번

리뷰

문제에 나와있는 그림 b 에서는

50, 50, 100, 60을 떼가야 260 최대 점수라는 예시 덕분에 풀 수 있었다.

	O		O
O		O		O

지그재그로 떼는 경우 뿐만 아니라,

자기와 다른 행의 옆옆 스티커를 뗐을 때 최대값을 발견할 수도 있다는 것이다.

	O			O
O		O

배열 S는 주어진 스티커 점수 배열이다.

배열 D를 D [행] [열] 이라고 하고, 해당 행과 열을 마지막으로 뗐을 때의 최대 스티커 점수를 저장한다.

하나의 열 마다 순회하는 for문을 만들고,

그 안에서 1행의 마지막일 경우의 최대값, 2행이 마지막일 경우의 최대값을 점화식으로 계산해서 D에 저장한다.

    //  D [행] [열]  
    D[1][i] = S[1][i] + max(D[2][i-1], D[2][i-2]);
    D[2][i] = S[2][i] + max(D[1][i-1], D[1][i-2]);

예를 들면,

D[1] [3] = 자기자신 S[2] [3] + max( D[2] [1] , D [2] [2] )

대각선으로 더했을 때 최대인지, 반대편 행의 옆옆 칸을 더했을 때 최대인지를 비교하면 된다.

코드

#include <stdio.h>
#include <algorithm>
using namespace std;

// 스티커 (BOJ 9465)

int S[3][100001]; // 입력받은 스티커 점수  
int D[3][100001];
int n, max_sum;

int Sticker(){

    // 1열 
    D[1][1] = S[1][1];
    D[2][1] = S[2][1];

    // 2열  
    D[1][2] = D[2][1] + S[1][2];
    D[2][2] = D[1][1] + S[2][2];

    for(int i = 3; i <= n; i++){

        D[1][i] = S[1][i] + max(D[2][i-1], D[2][i-2]);
        D[2][i] = S[2][i] + max(D[1][i-1], D[1][i-2]);
    }

    return max(D[1][n] , D[2][n]);
}

int main(void){

    int T = 0;
    int i = 0, num = 0;

    scanf("%d", &T);

    while(T--){

        scanf("%d", &n);

        for(i = 1; i <= n; i++){
            scanf("%d", &num);
            S[1][i] = num;
        }

        for(i = 1; i <= n; i++){
            scanf("%d", &num);
            S[2][i] = num;
        }

        printf("%d\n", Sticker());

    }

    return 0;
}