프로그래머스 스티커 모으기(2) (JAVA)

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

코딩테스트 연습 - 스티커 모으기(2)

 

저는 해당 문제를 DP를 이용해 문제를 해결하였습니다.

저는 첫번째의 값을 포함하고 있는지 안 포함하는지에 따라 다르게 DP를 저장하였습니다.

이유는 첫번째의 값을 포함하게 되면 마지막의 값을 포함할 수 없기 때문입니다.

 

import java.util.*;
class Solution {
    private static final int INCLUDE_FIRST = 0;
    private static final int NOT_INCLUDE_FIRST = 1;
    public int solution(int sticker[]) {
        int answer = 0;
        int size = sticker.length;
        if(size == 1){
            return sticker[0];
        }
        int[][] dp = new int[2][size];
        dp[INCLUDE_FIRST][0] = sticker[0];
        dp[INCLUDE_FIRST][1] = Math.max(sticker[0], sticker[1]);
        dp[NOT_INCLUDE_FIRST][1] = sticker[1];
        for(int i = 2 ; i < size ; i++){
            if(i != size-1){
                dp[INCLUDE_FIRST][i] = Math.max(dp[INCLUDE_FIRST][i-1], dp[INCLUDE_FIRST][i-2] + sticker[i]);
            }
            dp[NOT_INCLUDE_FIRST][i] = Math.max(dp[NOT_INCLUDE_FIRST][i-1], dp[NOT_INCLUDE_FIRST][i-2] + sticker[i]);
        }
        // System.out.println(Arrays.toString(dp[INCLUDE_FIRST]));
        // System.out.println(Arrays.toString(dp[NOT_INCLUDE_FIRST]));
        answer = Math.max(dp[INCLUDE_FIRST][size-2],dp[NOT_INCLUDE_FIRST][size-1]);
        return answer;
    }
}