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

문제

 

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

프로그래머스

문제풀이

 

연속으로 고르지 못하고 하나를 고르면 그 양 옆은 고를 수 없는 문제라 DP를 이용해 풀었다.

원형이기 때문에 2가지 경우로 나누어 문제를 풀었다.

 

첫 번째, 1차원 벡터로 봤을 때, 맨 앞을 선택할 때.

두 번째, 맨 앞을 선택하지 않을 때.

 

    sticker.insert(sticker.begin(), 0);
    sticker.insert(sticker.begin(), 0);
    sticker.insert(sticker.begin(), 0);

    vector<int>DP1(sticker.size(), 0);

    for (idx = 3; idx + 1 < sticker.size(); ++idx) {
        DP1[idx] = sticker[idx] + max(DP1[idx - 2], DP1[idx - 3]);
        answer = max(answer, DP1[idx]);
    }

첫 번째, 1차원 벡터로 봤을 때, 맨 앞을 선택할 때이다. 맨 앞을 선택했으므로 맨 끝 스티커는 탐색하지 않는다.

 

스티커를 고를 때 두 가지 경우로 고를 수 있다. 

idx번째 스티커를 무조건 고른다고 했을 때, OXO, OXXO 두 가지이다.

조건문을 편하게 작성하기 위해서 벡터의 맨 앞에 0을 3개를 추가했다. (idx-3 때문에)

 

반복문을 돌면서 OXO와 OXXO 둘 중 더 큰 수를 현재 idx 스티커 값을 더한 것을 저장한다.

answer = max(answer, DP1[idx1])를 통해 답을 갱신한다.

 

    sticker.erase(sticker.begin() + 3);

    vector<int>DP2(sticker.size(), 0);

    for (idx = 3; idx < sticker.size(); ++idx) {
        DP2[idx] = sticker[idx] + max(DP2[idx - 2], DP2[idx - 3]);
        answer = max(answer, DP2[idx]);
    }

두 번째 경우인 맨 앞을 선택하지 않을 때이다.

위에서 0을 3개를 추가했고, 4번 인덱스는 처음에 주어진 배열의 맨 앞값이다.

따라서 erase를 통해 해당 인덱스를 지운다.

그다음은 이전 반복문과 동일하다.

반복문이 끝났으면 answer을 return 한다.

코드

#include <vector>
using namespace std;

int solution(vector<int> sticker)
{
    int idx(0), answer(sticker[0]);

    sticker.insert(sticker.begin(), 0);
    sticker.insert(sticker.begin(), 0);
    sticker.insert(sticker.begin(), 0);

    vector<int>DP1(sticker.size(), 0);

    for (idx = 3; idx + 1 < sticker.size(); ++idx) {
        DP1[idx] = sticker[idx] + max(DP1[idx - 2], DP1[idx - 3]);
        answer = max(answer, DP1[idx]);
    }

    sticker.erase(sticker.begin() + 3);

    vector<int>DP2(sticker.size(), 0);

    for (idx = 3; idx < sticker.size(); ++idx) {
        DP2[idx] = sticker[idx] + max(DP2[idx - 2], DP2[idx - 3]);
        answer = max(answer, DP2[idx]);
    }

    return answer;
}