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

문제

---

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

풀이

---

스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대인, 최적해를 구하는 문제이므로 DP를 활용하여 풀이한다. 다만, 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 되므로, 시작 시 첫 번째 스티커를 뜯는 여부에 따라 나눠 DP를 진행하여 각각의 경우 중 최대 합을 return한다.

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

using namespace std;

int solution(vector<int> sticker)
{
    int answer = 0;
    
    vector<int>dp(sticker.size());

    if (sticker.size() == 1) return sticker[0]; 

    dp[0] = sticker[0];
    dp[1] = dp[0];

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

    int max_num = *max_element(dp.begin(), dp.end());

    dp[0] = 0;
    dp[1] = sticker[1];

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

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

    return answer;
}