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

프로그래머스의 스티커모으기(2)(Lv4) 문제이다.

[ 문제풀이 ]

스티커를 뜯어냈을 때, 뜯은 스티커들의 합이 최대가 되도록 하고 싶을 때, 그 값을 구해야 하는 문제이다.

먼저, 스티커는 원형판 형태로 존재한다. 따라서, 우리에게 주어지는 sticker라는 함수의 인자가 단순 vector라고 하더라도, 우리는 0번째 Index와 마지막 Index가 서로 인접해 있는 형태라 생각하고 문제를 풀어야 한다.

스티커를 뜯을 때, 그 합이 최대가 되는 과정을 알아보자.

Sum[] 이라는 배열을 이용해서 한번 표현해보자. Sum[a] = b의 의미는, "a번째 스티커까지 뜯었을 때, 얻을 수 있는 최대값은 b 입니다." 를 의미한다.

우리가 현재 'a번째 스티커'를 뜯는 상황을 생각해보자. a번째 스티커를 뜯을 때, 얻을 수 있는 최대값은 얼마가 될까 ??

여기서 우리는 2가지 값을 비교해 주면 된다.

1. a - 2번째 스티커를 뜯었을 때 얻을 수 있는 최대값 + a번째 스티커를 뜯음으로써 얻을 수 있는 스티커의 값

2. a번째 스티커를 뜯지 않고, a - 1번째 스티커를 뜯었을 때의 최대값

이 2가지 값을 비교해주면 된다.

a번째 스티커를 뜯는다는 것은, a - 1번째, a + 1 번째 스티커는 뜯지 못한다는 것을 의미하고, 이 스티커를 뜯었을 때 구할 수 있는 최대값은, a - 2번째 스티커까지 뜯었을 때의 최대값(Sum[a - 2]) + 스티커 a가 가지고 있는 값 이 된다.

반대로, 뜯지 않는다는 것은, a - 1번째, a + 1번째 스티커 또한 뜯을 수 있다는 것을 의미하고, 이 때 얻을 수 있는 최댓값은 a - 1번째 스티커까지 뜯었을 때의 최댓값(Sum[a - 1]이 된다.

우리는 이 2개의 값을 비교해서 더 큰 값으로 갱신해 나가면 된다.

그런데 ! 처음에 말했듯이, 0번 Index와 마지막 Index는 붙어있는 형태이다. 따라서, 0번 Index를 뜯게되면, 마지막 Index는 뜯을 수 없게되고, 반대로 0번 Index를 뜯지 않는다면, 마지막 Index는 뜯을 수 있게 된다.

그래서 본인은 위의 2가지 경우를 따로따로 계산해 주었다.

1. 0번 Index에 있는 스티커를 뜯고, 그 이후의 스티커를 뜯는 경우. (N - 1까지만 진행)

2. 0번 Index에 있는 스티커를 뜯지 않고, 그 이후의 스티커를 뜯는 경우. (N까지 진행)

결과적으로는 위 2가지 경우에서 더 큰 값을 정답으로 갱신해 주면 된다.

이 과정을 Dynamic Programming기법을 통해서 구현해 주었다. 점화식은 위에서 말한 2가지 값을 비교하는 것으로 설정해서 구현하였다.

[ 소스코드 ]

#include <vector>
using namespace std;
 
int DP[100010];
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
int solution(vector<int> sticker)
{
    int answer = 0;
    int N = sticker.size();
    if (N == 1) return sticker[0];
 
    DP[0] = sticker[0];
    DP[1] = sticker[0];
    for (int i = 2; i < N - 1; i++)
    {
        DP[i] = Bigger(DP[i - 2] + sticker[i], DP[i - 1]);
    }
    answer = Bigger(answer, DP[N - 2]);
    DP[0] = 0;
    DP[1] = sticker[1];
    for (int i = 2; i < N; i++)
    {
        DP[i] = Bigger(DP[i - 2] + sticker[i], DP[i - 1]);
    }
    answer = Bigger(answer, DP[N - 1]);
 
    return answer;
}