문제

문제링크

접근

• 처음에는 전형적인 dp문제라고 생각이 들었는데, 원형이라서 마지막 인덱스 처리하는 데에 꽤 고민을 많이 했다.
• 점화식 수준에서 분기할 수 있을 것 같아서 고민했는데, 두 경우의 따로 dp배열을 만들어서 마지막에 비교하니 해결되었다.

풀이

class Solution {
    public int solution(int sticker[]) {
        int size = sticker.length;
        if (size == 1) return sticker[0];

        int[] dp1 = new int[size];
        int[] dp2 = new int[size];

        dp1[0] = sticker[0];
        dp1[1] = sticker[0];
        dp2[1] = sticker[1];
        for (int i = 2; i < size; i++) {
            dp1[i] = Math.max(dp1[i-1],dp1[i-2] + sticker[i]);
            dp2[i] = Math.max(dp2[i-1],dp2[i-2] + sticker[i]);   
        }

        return Math.max(dp1[size-2], dp2[size-1]);
    }
}