참고

https://chosh95.tistory.com/371

https://coding-insider.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-4-%EB%8F%84%EB%91%91%EC%A7%88-CC-%E2%98%85

https://yabmoons.tistory.com/477

풀이전략

• 개미전사와 동일하다.
• 추가적으로 생각해야 할 부분이 첫번째를 선택할 경우, 마지막값과 인접하므로
  이를 어떻게 처리할지를 생각해야 한다.

핵심!

• 0번째 인덱스를 선택하면 마지막 -1까지 진행한다.
• 0번째를 선택 안하면 마지막까지 진행해도 된다.

소스코드

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

int solution(vector<int> money) {
    int answer = 0;

    vector<int>dp(money.size(), 0);
    vector<int>dp2(money.size(), 0);

    dp[0] = money[0];
    dp[1] = money[0];
    dp2[0] = 0;
    dp2[1] = money[1];


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

    for(int i = 2; i < dp2.size(); i++)
    {
        dp2[i] = max(dp2[i - 1] , dp2[i - 2] + money[i]);
    }

    int max1 = *max_element(dp.begin(), dp.end());
    int max2 = *max_element(dp2.begin(), dp2.end());

    if(max1 < max2)
    {
        answer = max2;
    }
    else
        answer = max1;


    return answer;
}