[프로그래머스] 스티커 모으기(2)

---

📌 문제 설명

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

 

🔗 문제 링크

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

프로그래머스

---

반응형

💡 풀이 아이디어

• 첫 번째 스티커와 마지막 스티커를 뜯는 경우 2가지로 나눈다.
• 현재 스티커를 뜯는 것이 합을 더 크게 만들 수 있는지 비교한다.

📝 최종 풀이

• 두 가지 경우 모두 초기에 뜯을 스티커를 설정합니다.
  • first의 경우 첫 번째와 두 번째 스티커 중 큰 값을 비교합니다.
  • last의 경우 마지막 스티커를 뜯어야 하기 때문에, 두 번째와 세 번째 스티커 중 큰 값을 비교합니다.
  • n = 1 인 경우를 고려하여 last[0]에 첫 번째 스티커 값을 저장합니다.
• 초기에 뜯은 스티커 이후로 나오는 스티커의 숫자가 뜯는 것이 이전 합보다 큰지 비교하여 갱신합니다.
• 최종적으로 두 가지 경우의 값 중 큰 값을 return 합니다.

---

728x90

👩‍💻 코드

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

int solution(vector<int> sticker)
{
    int n = sticker.size();
    
    vector<int> first(n, 0);
    first[0] = sticker[0];
    first[1] = max(sticker[0], sticker[1]);
    
    for (int i = 2; i < n - 1; i++) {
        first[i] = max(first[i-1], first[i-2] + sticker[i]);
    }
    
    vector<int> last(n, 0);
    last[0] = sticker[0];
    last[1] = sticker[1];
    last[2] = max(sticker[1], sticker[2]);
    
    for (int i = 3; i < n; i++) {
        last[i] = max(last[i-1], last[i-2] + sticker[i]);
    }
    
    return max(first[n-2], last[n-1]);
}