Level 3. 스티커 모으기(2)

Level 3. 스티커 모으기(2)

 

 

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

 

DP 문제라는 생각은 들었지만, 막상 풀이가 바로 떠오르지는 않았다.

 

DP 문제에서는 DP 테이블의 의미를 정확히 아는 것이 중요하다.

• 이 문제에서는 i번째까지 스티커를 때었을 때 최댓값을 저장한다.

 

처음에는 2가지를 고려해야 한다.

• 첫 번째 스티커를 뜯고 시작하거나, 뜯지 않고 시작하거나

 

진행하면서는 2가지를 고려한다.

• i번째 스티커를 뜯거나, 뜯지 않거나
• 뜯는 경우에는 DP[i] = DP[i - 2] + sticker[i]가 된다.

 

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

#define I(i) (((i) + n) % n)

using namespace std;

int solution(vector<int> sticker)
{
    if (sticker.size() <= 1)
        return sticker[0];

    size_t n = sticker.size();
    vector<int> d1(n, 0), d2(d1);

    d1[1] = d1[0] = sticker[0];
    
    for (int i = 2; i < n - 1; ++i)
        d1[i] = max(d1[i - 2] + sticker[i], d1[i - 1]);

    for (int i = 1; i < n; ++i)
        d2[i] = max(d2[I(i - 2)] + sticker[i], d2[i - 1]);

    return max(d1[I(-2)], d2[I(-1)]);
}