[level 3] 스티커 모으기(2) - 12971

[level 3] 스티커 모으기(2) - 12971

문제 링크

성능 요약

메모리: 6.99 MB, 시간: 0.77 ms

구분

코딩테스트 연습 > Summer／Winter Coding（～2018）

채점결과

정확성: 49.7
효율성: 50.3
합계: 100.0 / 100.0

제출 일자

2023년 11월 1일 17:49:34

문제 설명

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

원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.

예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.

제한 사항

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

---

입출력 예

sticker	answer
[14, 6, 5, 11, 3, 9, 2, 10]	36
[1, 3, 2, 5, 4]	8

입출력 예 설명

입출력 예 #1
6, 11, 9, 10이 적힌 스티커를 떼어 냈을 때 36으로 최대가 됩니다.

입출력 예 #2
3, 5가 적힌 스티커를 떼어 냈을 때 8로 최대가 됩니다.

 

코드

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

int solution(vector<int> sticker)
{
    int answer = 0;
    int size = sticker.size();
    if(size == 1)
        return sticker[0];

    vector<pair<int, int>> dp(size, pair<int, bool>(0, 0));
    //처음을 찢었을 때, 찢지 않았을 때
    dp[0] = pair(sticker[0], 0);
    dp[1] = pair(sticker[0], sticker[1]);
    //점화식 : dp[n] = max(dp[n-1], dp[n] + dp[n-2])

    //처음을 찢었다면 마지막 스티커까지의 최댓값을 구할 필요가 없고,
    //처음을 찢지 않았다면 마지막 스티커까지의 최댓값을 구해야 한다.
    //즉, 마지막 스티커 이전까지의 최댓값을 각각 구하고, 마지막 스티꺼를 포함하여 처음을 찢지 않았을 때의 최댓값을 추가로 구한 후 두 경우 중 최댓값을 구한다.
    for(int i = 2; i < size-1; i++)
    {
        int first = max(dp[i-1].first, sticker[i] + dp[i-2].first);
        int second = max(dp[i-1].second, sticker[i] + dp[i-2].second);
        dp[i] = pair(first, second);
    }
    dp[size-1] = pair(dp[size-2].first, max(dp[size-2].second, sticker[size-1] + dp[size-3].second));
    answer = max(dp[size-1].first, dp[size-1].second);
    return answer;
}

테스트 결과