Programmers : 스티커 모으기(2)

풀이 요약

DP (풀이 참조)

풀이 상세

1. 스티커의 인덱스를 $x$ 라고 하는 경우, $x$ 를 뜯고 다음 $x+1$ 을 뜯지 않을 것인지, $x$ 를 뜯지 않고, $x+1$ 을 뜯을 것인지를 확인한다.

2. $x$ 를 뜯는 경우, $x-1$ , $x+1$ 에은 사용되지 못하므로, $x$ 의 이전의 값은 $x-2$ 가 될 것이다. 이를 $x$ 를 뜯지 않는 경우는 자연스럽게 $x$ 의 이전의 값은 $x-1$ 이 된다. 따라서 이 두가지를 모두 정리하는 점화식을 세우면 max(dp[x-2]+sticker[x], dp[x-1]) 이 된다.

3. 여기에 추가로 처음 인덱스와 마지막 인덱스는 이어져 있으므로 맨 처음 인덱스를 뽑는 경우라면, 마지막 인덱스를 사용해서는 안된다. 이를 위해, 처음의 스티커를 뽑는 경우와 뽑지 않는 경우로 나눈 후, 첫 스티커를 뽑는 경우는 마지막 스티커를 보지 않도록 인덱스를 하나 줄이고, 뽑지 않는 경우는 마지막 인덱스까지 본다.

배운점

• DP는 늘 어렵다.

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 100000;
int sum[MAX+4];

int solution(vector<int> sticker)
{
    
    if(sticker.size()==1) return sticker[0];
    sum[0] = sticker[0];
    sum[1] = sticker[0];
    for(int i=2; i<sticker.size()-1; i++) {
        sum[i] = max(sum[i-2]+sticker[i], sum[i-1]);
    }
    int temp = sum[sticker.size()-2];
    sum[0] = 0;
    sum[1] = sticker[1];
    for(int i=2; i<sticker.size(); i++) {
        sum[i] = max(sum[i-2]+sticker[i], sum[i-1]);
    }
    return max(temp, sum[sticker.size()-1]);
}