백준 9465번. 스티커(c++) / dp

최대 100,000개의 열을 가질 수 있기 때문에 바로 dp로 풀었다.

생각해보면 (i, j)의 자리에 스티커를 붙이게 되면 변이 닿아 있는 부분은 훼손되기 때문에 결국 (i-1, j-1), (i-1, j-2)의 자리 중 큰 값에 붙이는 것이 이득이 된다.

 

따라서, 0행일 때는

dp[0][j] = max(dp[1][j-1], dp[1][j-2]) + sticker[0][j]라는 점화식이 나오고

 

1행일 때는

dp[1][j] = max(dp[0][j-1], dp[0][j-2]) + sticker[1][j]라는 점화식을 도출할 수 있다.

 

 

코드 첨부

// 스티커
#include <iostream>
#include <cstring>
using namespace std;
 
int testcase, n, final = 0;
int sticker[3][100002] = {0, };
int dp[3][100002] = {0, };
 
int main()
{
    cin>>testcase;
    for(int i=0; i<testcase; i++){
        memset(dp, 0, sizeof(dp));
        memset(sticker, 0, sizeof(sticker));
        final = 0;
        cin>>n;
        // 0행
        for(int j=1; j<=n; j++){
            cin>>sticker[0][j];
        }
        // 1행
        for(int j=1; j<=n; j++){
            cin>>sticker[1][j];
        }
 
        dp[0][0] = dp[1][0] = 0;
        dp[0][1] = sticker[0][1];
        dp[1][1] = sticker[1][1];
 
        for(int j=2; j<=n; j++){
            dp[0][j] = max(dp[1][j-1], dp[1][j-2])+sticker[0][j];
            dp[1][j] = max(dp[0][j-1], dp[0][j-2])+sticker[1][j];
        }
 
        final = max(dp[0][n], dp[1][n]);
        cout<<final<<"\n";
    }
}

 

문제 첨부

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

9465번: 스티커