프로그래머스) Lv4 - 스티커 모으기(2)

https://programmers.co.kr/learn/courses/30/lessons/12971

코딩테스트 연습 - 스티커 모으기(2)

DP로 해결했습니다.

첫번째 스티커를 떼는 경우(마지막 스티커를 뗄 수 없음)와 두번째 스티커를 떼는 경우(마지막 스티커를 뗄 수 있음)를 나눠 계산한 후, 그 중 최대 값이 답이 됩니다.

---

C++ 소스 코드

#include <vector>
#include <algorithm>
using namespace std;
int d[100001][2];
int solution(vector<int> sticker){
    int n = (int)sticker.size();
    if (n==1) return sticker[0];
    if (n==2) return max(sticker[0],sticker[1]);
    d[0][0] = sticker[0];
    d[1][0] = sticker[0];
    d[1][1] = sticker[1];
    for(int i=2;i<sticker.size();i++){
        d[i][0]= max(d[i-2][0]+sticker[i],d[i-1][0]);
        d[i][1]= max(d[i-2][1]+sticker[i],d[i-1][1]);
    }
    return max(d[n-2][0],d[n-1][1]);
}