https://programmers.co.kr/learn/courses/30/lessons/12971
코딩테스트 연습 - 스티커 모으기(2)
N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록
programmers.co.kr
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> sticker)
{
int answer = 0;
int dp[100002];
if (sticker.size() == 1) return sticker[0];
dp[0] = sticker[0];
dp[1] = sticker[0];
answer = sticker[0];
for (int i = 2; i < sticker.size() - 1; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i]);
answer = max(answer, dp[i]);
}
dp[0] = 0;
dp[1] = sticker[1];
answer = max(answer,sticker[1]);
for (int i = 2; i < sticker.size(); i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + sticker[i]);
answer = max(answer, dp[i]);
}
return answer;
}