[JAVA/DP] 프로그래머스 스티커 모으기(2)

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12971?language=java# 

프로그래머스

 

2. 풀이

• 스티커 판이 원형이므로 sticker[0]을 선택할 경우 sticker[n-1](n은 길이) 값을 선택할 수 없으며, sticker[n-1]을 선택할 경우 sticker[0]을 선택할 수 없다
• 따라서, sticker[0]을 선택하는 경우와 그렇지 않은 경우로 나눠 DP를 계산한다.
• 기본적으로 현재 위치에서 두 경우 중 유리한 값을 선택한다. 
  1. 현재 위치의 스티커를 떼는 경우 → dp[i-2] + sticker[i]
  2. 현재 위치의 스티커를 떼지 않는 경우 → dp[i-1]
• sticker[0]을 포함하는 경우에는
  • dp[0]과 dp[1]의 값 모두 sticker[0]의 값이며, 마지막 인덱스를 포함하지 않고 dp를 진행한다.
• sticker[0]을 포함하지 않는 경우
  • dp[0]의 값은 0, dp[1]의 값은 sticker[1]이며, 마지막 인덱스를 포함하여 dp를 진행한다.

 

3. 코드

class Solution {
    
    public int solution(int sticker[]) {
        
        if(sticker.length == 1) return sticker[0];
        if(sticker.length == 2) return Math.max(sticker[0], sticker[1]);
        
        // 0번 인덱스에서 시작하는 dp - 마지막 인덱스를 포함하지 않음
        int[] dp1 = new int[sticker.length]; // 최대값
        dp1[0] = sticker[0];
        dp1[1] = sticker[0];
        for(int i = 2; i < sticker.length - 1; i++){
            if(dp1[i-2] + sticker[i] > dp1[i-1]){
                dp1[i] = dp1[i-2] + sticker[i];
            }else{
                dp1[i] = dp1[i-1];
            }
        }
        
        // 0번 인덱스에서 시작하지 않는 dp - 마지막 인덱스 값 포함 가능
        int[] dp2 = new int[sticker.length]; // 최대값
        dp2[0] = 0;
        dp2[1] = sticker[1]; 
        for(int i = 2; i < sticker.length; i++){
            if(dp2[i-2] + sticker[i] > dp2[i-1]){
                dp2[i] = dp2[i-2] + sticker[i];
            }else{
                dp2[i] = dp2[i-1];
            }
        }

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