[프로그래머스/C++] 스티커 모으기

프로그래머스

 

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

using namespace std;

// dp 문제
// 합이 최대가 되려면 결국에 최대한 많은 스티커를 떼어내야함
// dp[i]에서 스티커를 뜯을건지 뜯지 않을건지 결정하며 각 구간마다 최댓값을 선택해야함
// 점화식은 dp[i] = max(dp[i-1], dp[i-2] + sticker[i])
// 배열에서 첫 번째 스티커를 선택했을 때와 두 번째 스티커를 선택했을 때를 나누어서 수행해야함
// 첫 번째 스티커를 선택했을 때는 마지막 스티커를 선택하지 못함 > 원형으로 이어져있기 때문
// 두 번째 스티커를 선택했을 때는 첫 번째 스티커를 선택하지 못하므로 제외해야함
// dp 배열 2개 만들고 따로 수행해주면 될듯

int dp1[100001];
int dp2[100001];
int solution(vector<int> sticker)
{
    int answer = 0;
    int length = sticker.size();
    
    if(length == 1) return sticker[0];
    
    // 첫 번째 스티커를 선택할 때
    dp1[0] = sticker[0];
    dp1[1] = sticker[0];
    
    // dp 수행
    for(int i = 2; i < length - 1; i++)
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + sticker[i]);
    
    answer = max(answer, dp1[length - 2]);
    
    // 두 번째 스티커를 선택할 때
    dp2[0] = 0;
    dp2[1] = sticker[1];
    
    // dp 수행
    for(int i = 2; i < length; i++)
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + sticker[i]);
    
    answer = max(answer, dp2[length - 1]);
    
    return answer;
}