[Summer/Winter Coding(~2018)] 스티커 모으기(2)

[Summer/Winter Coding(~2018)] 스티커 모으기(2)

🙋‍♂️ 들어가며

이 문제에서는 2가지 경우를 생각하고 최댓값을 비교해야한다 idx 0 선택 vs idx 0 미선택

그러면 0을 선택하면 0 ~ N-2

0 미선택 -> N-1 까지

✅ 코드

class Solution {
    public int solution(int sticker[]) {
        int N = sticker.length;
        
        // 1. 조기종료 처리
        if (N == 1) {
            int res = sticker[0];
            return res;
        }
        if (N == 2) {
            int res = Math.max(sticker[0], sticker[1]);
            return res;
        }
        
        // 0번째 idx 선택 -> idx : 0 ~ N-2
        // 0번째 idx 미선택 -> idx : ? ~ N-1
        
        int[] DP_x = new int[N];
        int[] DP_y = new int[N];
        
        // 2-1. 0번째 idx 선택
        DP_x[0] = sticker[0];
        DP_x[1] = DP_x[0];
        for (int i = 2; i < N-1; i++) {
            DP_x[i] = Math.max(DP_x[i-1], sticker[i] + DP_x[i-2]);
        }
        
        
        // 2-2. 0번째 idx 미선택
        // 1번째가 좋으면 1번째 idx를 계속 사용
        // 2번쨰가 좋으면 1번째 안사용하고 2번째 idx를 사용
        DP_y[1] = sticker[1];
        DP_y[2] = Math.max(sticker[1], sticker[2]);
        for (int i = 3; i < N; i++) {
            DP_y[i] = Math.max(DP_y[i-1], sticker[i] + DP_y[i-2]);
        }
        
        
        // 3. 정답 구하기
        int answer = Math.max(DP_x[N-2], DP_y[N-1]);
        
        return answer;
    }
}