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

해설

규칙을 만족시키면서 스티커를 뗄 때 스티커의 가장 큰 합을 구하는 문제이다.

동적 계획법을 이용하여 답을 구해보자.

dp[i][j][k]를 i번까지 스티커를 사용했을 때 얻을 수 있는 최대 합이라고 설정한다.

이때, j는 첫번째 스티커의 사용여부(0, 1), k는 i번째 스티커의 사용여부(0, 1) 이다.

 

i번째 스티커를 사용한다면 i-1번째 스티커는 사용할 수 없다.

따라서, dp[i][j][1] = dp[i-1][j][0] + sticker[i] 가 된다.

 

i번째 스티커를 사용하지 않는다면, i-1번째 스티커는 사용해도 되고 사용하지 않아도 된다.

따라서, dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]) 이다.

 

dp[n-1][j][k] 까지 구했을 때, 스티커는 원형이므로 0번째 스티커와 n-1번째 스티커를 중복해서 사용할 수 없다.

따라서, n-1번째까지 스티커를 사용했을 때 최대 합은 max(dp[n-1][0][0], dp[n-1][1][0], dp[n-1][0][1]) 이 된다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <climits>
#include <cctype>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int dp[100005][2][2];

int solution(vector<int> sticker) {

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

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

    for (int i=1; i<n; i++) {
        dp[i][0][0] = max(dp[i-1][0][0], dp[i-1][0][1]);
        dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1]);
        dp[i][0][1] = dp[i-1][0][0] + sticker[i];
        dp[i][1][1] = dp[i-1][1][0] + sticker[i];
    }

    return max({dp[n-1][0][0], dp[n-1][0][1], dp[n-1][1][0]});
}