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

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

코딩테스트 연습 - 스티커 모으기(2)

 

[난이도] level3
[유형] DP

[풀이]
첫번째 스티커를 떼면 마지막 N번째 스티커는 절대로 뗄 수 없고,
첫번째 스티커를 떼지 않으면 마지막 N-1번째 스티커에 따라 뗄 수 있을수도 없을수도 있습니다.

이를 이용해 첫번째 스티커를 뗀 경우와 안뗀 경우를 나눠서 생각하면 편합니다.

dp[n][f] 배열에서 f가 0이면 첫번째 스티커를 뗀 경우, 1이면 떼지 않은 경우로 생각하여 문제를 풉니다.

dp[n][f] (sol(n,f)) 의 의미는 n~N-1까지만 고하고, n번째 스티커는 뗄수도 있을 때, 얻을 수 있는 최댓값입니다.

top-down으로 진행했을 때 점화식은 아래와 같습니다.
sol(n,f) = max(sticker[n]+sol(n+2,f),sol(n+1,f))

sticker[n]+sol(n+2,f) : n번째 스티커를 뗐을 때입니다. n번 스티커의 수에 n+1번째 스티커는 뗄 수 없으므로 sol(n+2,f)를 더해줍니다.
sol(n+1,f) : n번째 스티커를 떼지 않았을 때이므로 1 건너뛰어 sol(n+2,f) 입니다.

마지막으로 n이 N-1이 되었을 때, f가 1이면 N-1번 스티커는 떼지 못하므로 0을 return, 0이면 뗄 수 있으므로 sticker[N-1]를 return 해줍니다.

 

#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int N,dp[100002][2];
vector<int> sticker;
int sol(int n,int f){
    if(n>=N) return 0;
    if(n==N-1) return f ? 0 : sticker[N-1];
    int& ret = dp[n][f];
    if(ret!=-1) return ret;
    ret=max(sticker[n]+sol(n+2,f),sol(n+1,f));
    return ret;
}
int solution(vector<int> _sticker)
{
    sticker=_sticker;
    N=sticker.size();
    memset(dp,-1,sizeof(dp));
    return max(sol(1,0),sol(2,1)+sticker[0]);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/스티커_모으기(2).cpp