Programmers - 스티커 모으기

---

title: Programmers - 스티커 모으기
date: 2022-08-19
tags:

• Algorithm
• DP

---

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

문제 요약

원형으로 이루어진 스티커가 존재한다. 어떠한 위치의 스티커를 뜯으면 양 옆에 위치한 스티커는 사용할 수 없다.
뜯은 스티커의 총 합이 최대가 될 때, 합을 return한다.

문제 풀이

처음에는 스티커의 개수가 작게 주어지는 줄 알고 DFS를 이용하였으나, 곧바로 시간 초과가 발생하였다.
스티커의 개수는 최대 100K로, DFS와 같은 방식으로는 시간 내에 해결할 수 없다고 판단하였다.
원형이 아닌 일자로 나열될 경우 DP를 사용하면 되는 문제이다.
약간 사고를 바꾸어 원형 스티커를 일자 스티커로 취급하여 문제를 해결하였다.


n개의 스티커가 존재한다. 0 , 1 , ... , n-2 , n-1 의 순서이다.
원형이므로 0과 n-1이 붙어있는 상황이다.
이를 일자로 취급하기 위해서는 0과 n-1을 분리하면 된다.
둘 중 하나를 뜯거나, 둘 다 뜯기지 않으므로 이를 각각 분리해준다.
하나만 뜯는다면 1 , 2 , ... , n-2 , n-1 과 0 , 1 , ... , n-3 , n-2 이다.
둘 다 뜯기지 않는다면 1 , 2 , ... , n-3 , n-2 이다.
가장 마지막 케이스는 결국 둘 중 하나만 뜯는 케이스의 일부이므로, 저 두 케이스에 대해서 DP로 최대합을 구해주면 된다.
한 가지 주의할 점은 마지막에 최대값이 어디에 존재하냐이다.
제일 마지막 스티커를 뜯는게 best일 수도 있고, 그 직전의 스티커를 뜯는게 best일 수도 있다.
DP를 사용할 경우 해당 스티커를 뜯을 때의 best이다.
그러므로 생각없이 DP의 마지막 원소를 return해주면 best 값을 보내주는 것이 아니다.


효율성 테스트를 포함하여 최대 약 0.5ms의 성능을 확인할 수 있었다.

프로그램

#include <vector>
#include <algorithm>

using std :: vector ;
using std :: max ;


int iGetBestSticker ( vector < int > & vSticker , int iStartIndex , int iEndIndex )
{
    vector < int > vTempDP ( 4 , 0 ) ;


    for ( int i = iStartIndex ; i < iEndIndex ; ++i )
    {
        vTempDP [ 0 ] = vTempDP [ 1 ] ;
        vTempDP [ 1 ] = vTempDP [ 2 ] ;
        vTempDP [ 2 ] = vTempDP [ 3 ] ;
        vTempDP [ 3 ] = max ( vTempDP [ 0 ] , vTempDP [ 1 ] ) + vSticker [ i ] ;
    }


    return max ( vTempDP [ 2 ] , vTempDP [ 3 ] ) ;
}

int solution ( vector < int > sticker )
{
    int iStickerSize = sticker.size () ;



    if ( 1 == iStickerSize )
        return sticker [ 0 ] ;


    return max ( iGetBestSticker ( sticker , 0 , iStickerSize - 1 ) , iGetBestSticker ( sticker , 1 , iStickerSize ) ) ;
}