[DAY87] Algorithm : Collecting stickers

원형으로 연결된 스티커를 뜯어 최댓값을 만드는 문제다. "인접한 것을 사용할 수 없다"는 조건에서 전형적인 DP 점화식을 유도해냈고, "원형"이라는 특수한 조건을 두 개의 일직선 문제로 쪼개어 해결했다.

---

❓ 문제 분석

• 목표: 인접한 스티커를 뜯지 않으면서 합이 최대가 되도록 선택하기.
• 제약 조건: 스티커 $N$은 최대 10만. 완전 탐색은 불가능하며 $O(N)$으로 해결해야 한다.
• 핵심 키워드: "원형으로 연결", "인접한 스티커 사용 불가", "최댓값".

---

💡 풀이 설계

1. 점화식 도출 (Recurrence Relation)

• $i$번째 스티커에 도착했을 때의 선택지는 두 가지다.
  1. 뜯는다: $i-1$번은 못 쓰므로, $i-2$번까지의 최댓값 + 현재 스티커 값. (dp[i-2] + sticker[i])
  2. 안 뜯는다: $i-1$번까지의 최댓값을 그대로 가져옴. (dp[i-1])
• 결론: dp[i] = max(dp[i-1], dp[i-2] + sticker[i])

2. 원형 구조 해결 (Circular Property)

• 원형이므로 0번과 N-1번은 동시에 뜯을 수 없다. 이를 해결하기 위해 문제를 두 가지 케이스로 분리한다.
  • Case 1 (0번 뜯음): 0번을 필수로 선택하되, 마지막 N-1번은 절대 선택하지 않는다.
    • 탐색 범위: 0 ~ N-2
  • Case 2 (0번 안 뜯음): 0번을 버리고, 1번부터 시작하여 마지막 N-1번을 고려한다.
    • 탐색 범위: 1 ~ N-1

---

💻 코드 구현

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> sticker)
{
    int answer = 0;
    int N = sticker.size();

    // 예외 처리: 스티커가 한 장뿐일 때
    if (N == 1) return sticker[0];

    // DP 테이블 초기화
    vector<int> dp1(N, 0); // Case 1: 첫 번째 스티커 뜯음
    vector<int> dp2(N, 0); // Case 2: 첫 번째 스티커 안 뜯음

    // Case 1 진행 (범위: 0 ~ N-2)
    dp1[0] = sticker[0];
    dp1[1] = sticker[0]; // 1번은 못 뜯으므로 0번 값 유지
    for (int i = 2; i < N - 1; ++i)
    {
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + sticker[i]);
    }

    // Case 2 진행 (범위: 1 ~ N-1)
    dp2[0] = 0;          // 0번 안 뜯음
    dp2[1] = sticker[1]; // 1번 뜯음
    for (int i = 2; i < N; ++i)
    {
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + sticker[i]);
    }

    // 두 케이스 중 최댓값 선택
    // Case 1의 끝은 N-2, Case 2의 끝은 N-1
    answer = max(dp1[N - 2], dp2[N - 1]);
    return answer;
}

---

🐛 시행착오 및 디버깅

• 문제점: $N=1$일 때 dp1[N-2] 접근 시 인덱스가 음수가 되어 런타임 에러가 발생할 수 있다.
• 해결: 함수 도입부에 if (N == 1) return sticker[0]; 예외 처리를 추가하여 방어했다.
• 포인트: 원형 문제를 풀 때는 "시작과 끝이 만나는 지점을 끊어서 두 개의 선형 문제로 만든다"는 아이디어가 핵심이다.

---

✅ 오늘의 회고

항목	내용
유형	DP (동적 계획법)
체감 난이도	중 (점화식만 세우면 구현은 쉬움)
복잡도	시간: $O(N)$, 공간: $O(N)$
새로 배운 것	원형 배열에서의 DP 접근법 (첫 요소를 포함하느냐 마느냐로 케이스 분리)