C++:: 프로그래머스 < 스티커 모으기(2) >

전형적인 dp문제이다. 주의해야할 점은 스티커가 원형으로 이어져있기 때문에 맨처음 스티커를 고르는 것과 아닌 것, 두가지의 경우에 대해 dp를 구해야 한다.

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

int solution(vector<int> sticker) {
    int answer = 0, n = sticker.size();
    vector<int> dp(sticker.size());  
    
    if (sticker.size() == 1) return sticker[0];
    // 맨 처음 스티커 골랐을때, 마지막 스티커 사용 x
    dp[0] = sticker[0];
    dp[1] = dp[0];
    for(int i = 2; i < n - 1; i++) {
        dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i]);
    }
    dp[n - 1] = dp[n - 2];
    answer = *max_element(dp.begin(), dp.end());
    // 맨 처음 스티커 안골랐을때, 마지막 스티커 사용 o
    dp[0] = 0;
    dp[1] = sticker[1];
    for(int i = 2; i < n; i++) {
        dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i]);
    }

    answer = max(answer, *max_element(dp.begin(), dp.end()));
    
    return answer;
}