Stickers 백준 - 9465번

오늘은 9465번을 풀어봤습니다.

이전과 동일한 dp문제입니다. 의도치는 않지만, 계속 dp문제만 풀게 되네요.

이번 dp는 (0,0),(0,1),(1,0),(1,1)들을 arr값들로 채우고, top을 (0,n-1),(1,n-1)들로 잡은뒤, 올라가면서, 최댓값을 계속 구하는 방법으로 풀었습니다.

임의의 dp[0][k]에서 최댓값은 두가지로 나뉩니다. 하나는 dp[1][k-1] + arr[0][k]이고, 남은 하나는 dp[1][k-2] + arr[0][i]입니다. 따라서 코드는 아래와 같습니다.

int n;
vector<vector<int>> arr;
vector<vector<int>> dp;

void dfs(){
    for(int i =2;i<n;i++){
        dp[0][i] = max(dp[1][i-1],dp[1][i-2]) + arr[0][i];
        dp[1][i] = max(dp[0][i-1],dp[0][i-2]) + arr[1][i];
    }
}
void solve(){
    cin>>n;
    arr = vector<vector<int>>(2,vector<int>(n));
    dp =vector<vector<int>>(2,vector<int>(n));
    int a;
    rep(i,2){// for문
        rep(j,n){
            cin>>a;
            arr[i][j] = a;
        }
    }
    dp[0][0] =arr[0][0];
    dp[1][0] =arr[1][0];
    dp[0][1] = arr[1][0] + arr[0][1];
    dp[1][1] = arr[1][1] + arr[0][0];
    dfs();
    cout<<max(dp[0][n-1],dp[1][n-1])<<endl;
}
int main() {
    fast_io;
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

 

www.acmicpc.net/problem/9465