프로그래머스 - 스티커 모으기(2) (C++)

문제 설명

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

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

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

제한 사항

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

 

뭐 https://programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

이 문제랑 거의 똑같은 문젠데 조건 1개만 추가 됐을 뿐이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
long long dp1[100001], dp2[1000001];
 
int solution(vector<int> sticker)
{
    int len = sticker.size();
    dp1[0] = sticker[0];
    dp1[1] = sticker[0];
    dp2[0] = 0;
    dp2[1] = sticker[1];
    
    if (len == 1)
        return sticker[0];
    
    for(int i=2;i<len - 1;i++)
        dp1[i]=max(dp1[i-2]+sticker[i],dp1[i-1]);
        
    for(int i=2;i<len;i++)
        dp2[i]=max(dp2[i-2]+sticker[i],dp2[i-1]);
   
 
 
    return max(dp1[len - 2], dp2[len - 1]);
}

 

 

배열의 길이가 1이면 그냥 그 값을 리턴한다.

원형 모양이라 했으니 첫 번째를 선택했을 경우와 선택 안했을 경우로 나누어 DP로 max값을 구해 나간다.

행렬 두개를 선언했으니 그 두개의 최종값 중 큰거를 리턴하면 된다.