BOJ 9465번 :: 스티커

#문제

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

9465번: 스티커

 

#작성 코드

TOP-DOWN

#include <iostream>
using namespace std;
 
int t, n;
int sticker[2][100000];
int dp[100000][3];
            //[0] : 이전 열에서 아무것도 떼지 않았음
            //[1] : 이전 열에서 상단 스티커를 뗐음
            //[2] : 이전 열에서 하단 스티커를 뗐음 
 
int cal(int col, int status){
    if( col==n )
        return 0;    // n+1열에는 뗄 스티커가 존재하지 않으므로 0을 리턴. 
    if( dp[col][status]!=-1)
        return dp[col][status];
    
    // 1. 아무것도 떼지 않고 다음 열으로 넘어가는 경우 
    int result = cal(col+1, 0);
    // 2. 이전 열의 하단 스티커를 떼지 않았을 경우 -> 하단 스티커도 뗄 수 있다  
    if( status!=2 ){
        result = max(result, sticker[1][col]+cal(col+1, 2));
    }
    // 3. 이전 열의 상단 스티커를 떼지 않았을 경우 -> 상단 스티커도 뗄 수 있다 
    if( status!=1 ){
        result = max(result, sticker[0][col]+cal(col+1, 1));
    }
    return dp[col][status] = result; 
}
 
int main(){
    cin>>t;
    while(t--){
        // dp배열을 -1로 초기화한다. 
        for(int i=0; i<100000; i++){
            for(int j=0; j<3; j++){
                dp[i][j] = -1;
            }
        }
        cin>>n;
        for(int i=0; i<2; i++){
            for(int j=0; j<n; j++){
                cin>>sticker[i][j];
            }
        }
        
        // 0열. 0열 이전 열에서 아무것도 떼지 않은 상태에서 시작한다. 
        cout<<cal(0, 0)<<'\n';
    }
    return 0;
}

 

##

2n개의 스티커 중, 스티커를 최대한 많이 뗀다면 n개의 스티커를 뗄 수 있다.

이렇게 생각하면 2개의 선택지밖에 없고, 최적해가 포함되지 않는 경우가 발생할 수도 있다.

-> 모든 경우를 살펴보아야한다.

dp[col][status]에 현재까지 뗀 스티커의 가치의 합을 저장한다.

status = col-1열에서 스티커를 뗀 상태

           : 0 = col-1에서 스티커 안뗐음

           : 1 = col-1 상단 스티커 뗐음

           : 2 = col-1 하단 스티커 뗐음

dp[col][status] 배열은 계산 중에 나타날 수 없는 값인 -1로 초기화하고, 이미 계산된 값을 요구한다면 메모이제이션 한 값을 리턴해준다.