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

스티커 모으기(2)

문제) https://programmers.co.kr/learn/courses/30/lessons/12971

풀이)

dp를 이용해서 풀어야 하는 문제다

점화식

dp[i] = i번째 스티커를 뗄 경우, 지금까지 얻을 수 있었던 점수의 최대값

dp[i] = max(dp[i-2] + sticker[i], dp[i-1]) 

//i번째 스티커를 뗄 경우, i-2번째 스티커를 뜯어낸 후 합쳐왔던 점수에 i번째 스티커 점수 합침 

  i번째 스티커를 떼지 않을 경우, i-1번째 스티커를 뜯어낸 후 합쳐왔던 점수 가져옴

* 주의점 *

원형으로 연결되어 있기에, 첫번째 스티커를 뜯어낼 경우 마지막 스티커를 뜯지 못한다.

이를 위해 첫번째 스티커를 뜯었을 경우와 아닐 경우를 나눠서 계산해본다.

코드)

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

int result = 0;

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

    if(sticker.size()== 1) return sticker[0];
    else if(sticker.size()==2) return max(sticker[0],sticker[1]);
    vector<int> dp(sticker.size(),0);

    //0번째 스티커 제거 -> 마지막 스티커 제거 못함
    dp[0] = sticker[0];
    dp[1] = sticker[0]; //0번째 제거 시 1번째는 제거 못함
    for(int i = 2; i < sticker.size()-1; i++){
        dp[i] = max(dp[i-2] + sticker[i] , dp[i-1]);//i번째 스티커를 제거할 경우, 제거하지 않을 경우
    }

    answer = dp[sticker.size() - 2];

    dp.resize(sticker.size()); //dp 배열 재사용

    //0번째 스티커 제거 안함 -> 마지막 스티커 제거 가능
    dp[0] = 0;
    dp[1] = sticker[1];
    for(int i = 2; i < sticker.size(); i++){
        dp[i] = max(dp[i-2] + sticker[i], dp[i-1]);
    }

    answer = max(answer, dp[sticker.size()-1]);

    return answer;
}