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

문제 접근

스티커를 떼면, 좌우 스티커를 더이상 먹지 못함.
이걸 고려하면, 크게 두가지 경우로 나눌 수 있음.
1. 0번을 먹은 경우 -> 1번을 먹지 못함, 마지막 요소인 N-1번도 못먹음.
2. 1번을 먹은 경우 -> 0번과 2번을 먹지 못함

그리고 추가로, 위 두 경우를 고려하면 자연스럽게 한 가지 경우가 더 나옴.
3. 0번과 1번 둘 다 먹지 않은 경우

위 1번 2번 케이스만으로는 둘 다 안먹은 걸 표현이 불가능함.

우선, N이 10만임. 따라서 N^2은 안되고, 자연스럽게 dp를 떠올려야 함.

dp 점화식

dp[i] 는 i번째까지 고려했을때(i번을 먹었다는 의미가 아님)의 최댓값을 의미한다.
따라서, 점화식은 다음과 같이 정의된다.

dp[i] = max(dp[i-1], dp[i-2]+sticker[i])
즉, i번째를 선택하지 않는다면 dp[i]은 dp[i-1]과 같을 것이고, i을 선택한다면 i-1번째를 선택하지 못하므로 dp[i-2]에서 i번째 요소 값을 더한것이 된다. 이중에서 더 큰 값이 dp[i]가 되는 것이다.

문제 풀이

import java.util.*;

class Solution {
    public int solution(int sticker[]) {
        int answer = 0;
        if(sticker.length <= 3) {
            int max = 0;
            for(int i=0; i<sticker.length; i++){
                max = Math.max(max, sticker[i]);
            }
            return max;
        }
        
        // 0번을 뜯은 경우, 마지막과 1번 아이템은 더이상 먹을 수 없음. 따라서, 1번까지 고려해도 최대는 sticker[0]임.
        int[] dp = new int[sticker.length-1];
        dp[0] = sticker[0];
        dp[1] = sticker[0];
        for(int i=2; i<sticker.length-1; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + sticker[i]);
        }
        answer = dp[sticker.length-2];
        
        // 1번을 뜯은 경우, 0번과 2번 아이템은 더이상 먹을 수 없음. 따라서, 2번까지 고려해도 최대는 sticker[1]임.
        dp = new int[sticker.length];
        dp[1] = sticker[1];
        dp[2] = sticker[1];
        for(int i=3; i<sticker.length; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + sticker[i]);
        }
        answer = Math.max(answer, dp[sticker.length-1]);
        
        // 0번과 1번 모두 뜯지 않은 경우, 이렇게 되면 2번은 자동으로 무조건 먹어야 함.
        dp = new int[sticker.length];
        dp[0] = 0;
        dp[1] = 0;
        for(int i=2; i<sticker.length; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + sticker[i]);
        }
        answer = Math.max(answer, dp[sticker.length-1]);
        return answer;
    }   
}