9465_스티커

Concept & Idea

문제 접근을 어떻게 할까 하다가 앞에 요소를 체크하려 했는데, 결국 과거의 값을 되돌아 생각해보는 것으로 생각해보니 해결되었다.

row가 0일 경우에, row가 1이고 && col이 자기 자신보다 -1,-2인 값중 큰 값을 누적하여 더한다.row가 1일 경우에, row가 0이고 && col이 자기 자신보다 -1,-2인 값중 큰 값을 누적하여 더한다.

DP배열에는 누적으로 최대값을 쌓아가고, 최종적으로 마지막 col의 최댓값을 출력하면 해결되는 문제였다.

Code

#include <iostream>
using namespace std;
int t;
int map[2][100001];
int cnt=0;
int dp[2][100001];
int main() {
    cin>>t;
    for(int i=0; i<t; i++) {
        int n;
        cin>>n;
        for(int r=0; r<2; r++) {
            for(int j=0; j<n; j++) {
                cin>>map[r][j];
            }
        }
        dp[0][0]=map[0][0]; dp[1][0]=map[1][0];
        if(n>1) {
            dp[0][1]=map[0][1]+map[1][0];
            dp[1][1]=map[1][1]+map[0][0];
        }
        for(int j=2; j<n; j++) {
            for(int r=0; r<2; r++) {
                if(r==0) {
                    dp[r][j]=map[r][j]+max(dp[1][j-2], dp[1][j-1]);
                } else if(r==1){
                    dp[r][j]=map[r][j]+max(dp[0][j-2], dp[0][j-1]);
                }
            }
        }
        cout<<max(dp[0][n-1],dp[1][n-1])<<endl;
    }
}

 

Fealing

다이나믹 프로그래밍 문제를 한번에 스스로 맞춰버렸다😆
정말 너무 기분이 좋구만!!