[프로그래머스] Level 3. 스티커 모으기

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

프로그래머스

 

해결 방법

완전탐색을 진행하기에는 sticker의 크기가 매우 크기 때문에, DP를 이용해 푼다.  원리는 다음과 같다. 예시와 함께 보자

 

 

dp[i] 는 i번째 인덱스까지의 스티커 중 나올 수 있는 최대값이다.

dp[0] = 0번째까지중 조합가능한 최대이므로, 14이다.

dp[1] = 1번째까지중 최대이므로, 14와 6중 큰 값이다.

dp[2] = 아래 두 경우중 더 큰 수를 고른다.

 

1.  dp[1] 은 6까지 포함될 수 있는 조합 중 가장 큰수이므로, 6까지 포함되고 5가 포함되지 않는경우 = dp[1]
2. dp[0] 은 sticker[1] , 즉 6이 포함되지 않았음이 보장되므로, 6이 포함되지 않고 5가 포함되는경우 = dp[0] + 5

따라서 dp[i] = max(dp[i-2]+sticker[i], dp[i-1]) 이다. 

 

 

여기서 주의할 사항은, 스티커가 원형으로 붙어있다는것이다. 위 공식대로 dp를 진행할 경우, 첫번째 스티커와 마지막 스티커가 둘다 선택되는 경우가 걸러지지않는다.  따라서 우리는 dp를 2개 구해야한다.

1. 첫번째 스티커를 고르고, 마지막스티커를 고르지않는다. (dp1)
2. 첫번째 스티커를 고르지않고, 마지막 스티커를 고른다(dp2)

dp1의 경우, 조사하는 범위를 0 <= i < sticker.size()-1 까지 조사한다.

dp2의 경우, 조사하는 범위를 1 <=i < sticker.size() 까지 조사한다.

 

이렇게 했을때 나오는 dp의 마지막요소들을 비교해서, 둘중 큰수를 반환한다.

 

#include <iostream>
#include <vector>
using namespace std;

int solution(vector<int> sticker)
{
    if(sticker.size() ==1) return sticker[0];
    if(sticker.size() ==2) return max(sticker[0], sticker[1]);
    
    vector<int> dp1 (sticker.size(),0);//첫번째요소 ~ 마지막꺼 빼고
    vector<int> dp2 (sticker.size(),0); //처음요소빼고, 마지막꺼포함
    
    dp1[0] = sticker[0]; dp1[1] = max(sticker[0],sticker[1]);
    dp2[0] = sticker[1]; dp2[1] = max(sticker[1], sticker[2]);
    for(int i=2; i<sticker.size()-1; i++){ 
        dp1[i] = max(dp1[i-2]+sticker[i], dp1[i-1]); //마지막요소는 고르지않음.
        dp2[i] = max(dp2[i-2]+sticker[i+1], dp2[i-1]);//두번째요소부터 넣엇음.
    }
    
    return max(dp1[sticker.size()-2],dp2[sticker.size()-2]);
}