[C++] 스티커문제 - dp

    //스티커가 1개일때 
    // dp문제는 1개 / 2개 일때 먼저 출력할 수 있으면 출력하자

#include <iostream>
#include <vector>
using namespace std;

int solution(vector<int> sticker)
{
    int answer =0;
    int n = sticker.size();
    vector<int> dp1(n,0);
    vector<int> dp2(n,0);
    
    // dp1 14부터 
    for (int i = 1; i < n; i ++){
        dp1[i] = sticker[i-1];
    }
    for (int i = 1; i < n; i ++){
        dp2[i] = sticker[i];
    }
    
    for(int i = 2; i < dp1.size(); i++){

        dp1[i] = max(dp1[i-1],dp1[i-2] + dp1[i]);
    }
    
    for(int i = 2; i < dp2.size(); i++){
        dp2[i] = max(dp2[i-1],dp2[i-2] + dp2[i]);
    }
    answer = max(dp1[dp1.size()-1],dp2[dp2.size()-1]);
    
    //스티커가 1개일때 
    // dp문제는 1개 / 2개 일때 먼저 출력할 수 있으면 출력하자

    if (n == 1){
        return sticker[0];
    }
    return answer;
}

 

로직 참고

https://sillon-coding.tistory.com/424

Programmers / 스티커 모으기(2) / Python 파이썬