[프로그래머스/Level 3/C++/Summer,Winter Coding] 스티커 모으기(2)

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

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

 

[문제 요약]

- N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.

- 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다.

- 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.

 

[문제 조건]

• sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.
• sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.
• 원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.

 

[문제 풀이]

이번 문제는 DP를 이용하여 해결이 가능하다.

 

핵심이 되는 아이디어는 12시 경계선 기준으로 오른쪽을 첫 번째 스티커라고 가정할 때, 첫 번째 스티커를 뜯냐 안뜯냐에 따라 나누어 생각하면 쉽게 풀 수 있다. 왜냐하면 첫 번째를 뜯어버리면 마자막 스티커는 아예 선택이 불가능하기 때문에, 마지막 스티커를 사용하는 경우도 생각해야 되기 때문에 나누어 생각할 수 밖에 없다.

 

따라서 위의 기준으로 인덱스로 표현하면 [1,2,3,4,5,6,7] 스티커를 이용한 값 하나, [2,3,4,5,6,7,8] 스티커를 이용한 값을 구해서 두 값 중 큰 값이 정답이 된다.

 

그 다음으로는 점화식을 생각해보도록 하자.

 

i번째 스티커를 사용하느냐 안하느냐에 둘 중 큰 값으로 저장할 것이다.

- 만약 i번째 스티커를 사용하지 않는다면 dp[i-1]의 값을 가질 것이다.

- 만약 i번째 스티커를 사용한다면 dp[i-2] + sticker[i]의 값이 될 것이다. 왜냐하면 i번째를 사용하면 i-1번째는 사용하면 안되기 때문이다. 

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

 

[소스 코드]

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

int solution(vector<int> sticker)
{
    int answer =0;
    vector<vector<int>> dp; dp.resize(2);
    for(int i=0; i<2; i++) dp[i].resize(sticker.size());
    
    if(sticker.size() == 1) return sticker[0];
    if(sticker.size() == 2) return max(sticker[0], sticker[1]);
    
    dp[0][0] = sticker[0];
    dp[1][1] = sticker[1];
    
    for(int i=1; i<sticker.size()-1; i++)
    {
        if(i==1)
        {
            dp[0][i] = max(sticker[i], dp[0][i-1]);
            dp[1][i+1] = max(sticker[i+1], dp[1][i]);
        }
        
        dp[0][i] = max(dp[0][i-1], dp[0][i-2] + sticker[i]);
        dp[1][i+1] = max(dp[1][i], dp[1][i-1] + sticker[i+1]);
    }

    return max(dp[1][sticker.size()-1], dp[0][sticker.size()-2]);
}

굳