9465

백준 9465번

Link: 9465번: 스티커

---

문제 설명

무난한 DP 문제였다.

예전에 풀어봤던 RGB 거리 문제처럼 바로 앞에서 선택한 인덱스를 제외한 나머지 인덱스의 DP값들에 스티커 점수를 더해가며 DP 배열을 채우면 되는 문제다.

확실히 이젠 DP에 대해서 감이 좀 생긴 느낌이 든다.

보다보니 비슷한 문제였다는게 보이네 슬슬ㅎㅎㅎ

---

정답 코드

//
// Created by Keith_Lee on 30/03/2019.
//

#include <iostream>
#include <strings.h>

using namespace std;

int T;
int stickers[2][100001] = {0, };
int DP[100001][3] = {0, };

int main(){
    cin >> T;

    for(int test=0; test<T; test++){
        int N;

        cin >> N;

        bzero(stickers, sizeof(stickers));
        bzero(DP, sizeof(DP));

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

        for(int i=1; i<=N; i++){
            DP[i][0] = max(max(DP[i-1][0], DP[i-1][1]), DP[i-1][2]);
            DP[i][1] = max(DP[i-1][0], DP[i-1][2]) + stickers[0][i];
            DP[i][2] = max(DP[i-1][0], DP[i-1][1]) + stickers[1][i];
        }

        cout << max(max(DP[N][0], DP[N][1]), DP[N][2]) << '\n';
    }

    return 0;
}

---