BOJ 9465번: 스티커

문제

문제 바로가기> BOJ 9465번: 스티커

9465번: 스티커

 

풀이

다이나믹을 이용해서 푸는 문제였다. 

dp[i][j-1] + dp[1][j]가 dp[2][j] 보다 작은 경우 dp[1][j-2] + dp[2][j]를 해주는 것이 최대값이 된다. 이를 i가 1인 경우와 2인 경우로 나누어 각각의 위치에서 스티커의 점수를 더하여 얻을 수 있는 최대값을 구해주었다!

 

#include<iostream>
#define MAX 100001
using namespace std;

int N;
int dp[3][MAX];
int sticker[3][MAX];

void input(){
    cin >> N;
    for(int i=1; i<=2; i++){
        for(int j=1; j<=N; j++){
            dp[i][j] = 0;
            cin >> sticker[i][j];
        }
    }
}

void solution(){
    
    dp[1][1] = sticker[1][1];
    dp[2][1] = sticker[2][1];

    for(int j=2; j<=N; j++){
        dp[1][j] = max(dp[2][j-2], dp[2][j-1]) + sticker[1][j];
        dp[2][j] = max(dp[1][j-2], dp[1][j-1]) + sticker[2][j];
    }
    cout << max(dp[1][N], dp[2][N]) << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    while(T--){
        input();
        solution();
    }
}