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

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

DP[i]가 의미하는 것은 i번째에서의 최대값이다.
이는 DP[i-1]번째 값을 그대로 사용하거나 DP[i-2]번째 값에 Sticker[i]를 더한 값 중 더 큰 값을 사용하면 된다.

단, 맨 처음과 맨 끝이 연결되어 있기 때문에 0번째를 선택하고 DP를 하는 것과 1번째를 선택하고 DP를 하는 것의 범위에 차이가 있다. (0번째를 선택하면 마지막 것을 선택할 수 없기 때문에 N개의 원소라고 가정하면 N-1까지만 DP를 해줘야 한다)
따라서 1번째 스티커를 선택하고 DP를 한 것과 0번째 스티커를 선택하고 DP를 한 결과 중 최대값을 반환하면 된다.

코드는 아래와 같다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> sticker)
{
    if(sticker.size() == 1)
        return sticker[0];
    
    vector<int> dp(sticker.size(), 0);
    dp[1] = sticker[1];
    for(int i=2;i<sticker.size();i++) 
        dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i]);
    
    vector<int> dp2(sticker.size(), 0);
    dp2[0] = sticker[0];
    dp2[1] = dp2[0];
    for(int i=2;i<sticker.size()-1;i++) 
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + sticker[i]);
    
    int c1 = *max_element(dp.begin(), dp.end());
    int c2 = *max_element(dp2.begin(), dp2.end());
    
    return max(c1, c2);
}