문제출처: https://programmers.co.kr/learn/courses/30/lessons/12971

문제

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

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

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

제한 사항

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

풀이

이 문제는 전에 풀었던 같은 lv.4의 도둑질 문제와 제한 사항을 제외하곤 아예 똑같다. 그래서 똑같이 dp를 사용하여 풀었다. 포인트는 첫번째 스티커를 뜯었을 경우에는 마지막 스티커를 뜯지 못하기 때문에, 첫번째 스티커를 뜯었을 경우와 뜯지 않았을 경우, 두개의 dp를 사용하여 풀어야한다.

코드

class Solution {
    public int solution(int sticker[]) {
        if (sticker.length <= 3) {
            int max = 0;
            for (int i = 0; i < sticker.length; i++) {
                max = Math.max(max, sticker[i]);
            }
            return max;
        }
        int[] dp1 = new int[sticker.length]; //첫번째부터 시작 (마지막 스티커 못 더함)
        int[] dp2 = new int[sticker.length]; //두번째부터 시작 (마지막 스티터 더하기 가능)
        dp1[0] = sticker[0];
        dp1[1] = sticker[0];
        dp2[0] = 0;
        dp2[1] = sticker[1];
        for (int i = 2; i < sticker.length - 1; i++) {
            dp1[i] = Math.max(dp1[i - 2] + sticker[i], dp1[i - 1]);
            dp2[i] = Math.max(dp2[i - 2] + sticker[i], dp2[i - 1]);
        }
        int i = sticker.length - 1;
        dp1[i] = Math.max(dp1[i - 1], dp1[i - 2]);
        dp2[i] = Math.max(dp2[i - 2] + sticker[i], dp2[i - 1]);
        
        return Math.max(dp1[i], dp2[i]);
    }
}