[Level 3] - 스티커 모으기2

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

프로그래머스

생각해 보기

1. 최대값을 찾아야 하므로 dp로 진행을 하자.
2. 현재 스티커가 들어간다는 가정하에 dp[i] = max(dp[i-2]+sticker[i], dp[i-1])가 성립한다.
3. 맨 처음 스티커가 들어가는 경우 dp[i][0] 안들어 가는 경우 dp[i][1]로 진행하자.(맨 뒷 부분이 들어가면 안되기에 구분을 한다.)

코드

#include <vector>
#include <algorithm>

using namespace std;

int dp[100001][2];

int solution(vector<int> sticker)
{
    int answer = 0;
    
    if(sticker.size() == 1)
        return sticker[0];
    
    dp[0][0] = sticker[0];
    dp[1][0] = sticker[0];
    dp[1][1] = sticker[1];

    for(int i=2;i<sticker.size();++i){
        dp[i][1] = max(dp[i-2][1]+sticker[i],dp[i-1][1]);
        
        if(i < sticker.size()-1)
            dp[i][0] = max(dp[i-2][0]+sticker[i],dp[i-1][0]);
    }

    answer = max(dp[sticker.size()-2][0],dp[sticker.size()-1][1]);
    return answer;
}