[프로그래머스/C++] 스티커 모으기

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 하나의 스티커를 떼면 양옆의 스티커를 사용할 수 없게 된다.

원으로 이어진 스티커를 위와 같이 직선으로 생각해 보자.

만약 첫번째 스티커를 뗀다면 마지막 스티커는 원형이므로 첫번째 스티커와 붙어있어 뗄 수 없게 된다.

하지만 첫번째 스티커를 그대로 둔다면 마지막 스티커를 뗄 수 있게 된다.

 

그러므로 2가지 경우를 생각해 각각 계산하고, 첫번째 스티커를 떼는 경우가 스티커 숫자의 합이 높은지 안떼는 경우가 스티커 숫자의 합이 높은지 계산하면 된다.

 

이제 어떤 스티커를 떼야하는지는 어떻게 알 수 있을까?

 

스티커가 위 그림처럼 나열되어 있을 때, i번째 스티커를 떼려면 i - 1번째 스티커는 떼지 않은 상태여야만 i번째 스티커를 뗄 수 있다.

 

이를 이용하면 ai번째에서 스티커를 떼거나 붙이는 경우를 고려할 때, 최대 값은 아래와 같이 나타낼 수 있다.

$$a_i \, =\,max(a_{i-1},\, a_{i-2} + sticker_i)$$ 

 

즉 이전에 해결한 i-1번째 까지 스티커를 붙이거나 떼는 경우의 최댓값을 이용해  i번째까지 스티커를 붙이거나 떼는 경우의 최댓값을 구할 수 있기 때문에 DP로 풀 수 있다.

 

​

[아이디어 정리]

1. 스티커가 원형이므로 첫번째 스티커를 붙이는 경우와 떼는 경우로 나눠서 각 경우의 최댓값을 구한다.
2. 각 경우의 최댓값을 구하는 방법은 a_i번째 스티커는 [a_(i-1)까지 구한 최댓값,  a_(i-2)+스티커의 수] 중 최댓값을 고르면 된다.
3. 두 경우의 최댓값을 비교하고 더 큰 값을 return한다.

 

Code

 

 

#include <vector>
using namespace std;

int solution(vector<int> sticker)
{
    if (sticker.size()==1)
        return sticker[0];
    int answer =0;
    vector<int> DP(sticker.size(),0);
    // 첫 스티커를 사용하는 경우 -> 마지막 포함 x
    DP[0]=sticker[0],DP[1]=sticker[0];
    for (int i=2; i<sticker.size()-1; i++)
    {
        DP[i]=max(DP[i-1],DP[i-2]+sticker[i]);
    }
    answer=DP[sticker.size()-2];
    // 첫 스티커를 사용하지 않는 경우 -> 마지막 포함 가능
    DP=vector<int>(sticker.size(),0);
    DP[1]=sticker[1];
    for (int i=2; i<sticker.size(); i++)
    {
        DP[i]=max(DP[i-1],DP[i-2]+sticker[i]);
    }
    answer=max(answer,DP[sticker.size()-1]);
    return answer;
}

 

---

 

경우를 잘 나눠서 생각하면 쉽게 풀 수 있는 문제였다.

 

 

프로그래머스