문제 - 스티커 모으기(2)

문제 접근

보자마자 이전에 풀어봤던 문제와 비슷해서 DP임을 알았지만.. 어떻게 접근해야될지 이해가 되지 않아서 다른사람이 푼 문제풀이를 보고 이해를 했다.

원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다. 라는 문구때문에 0번 인덱스의 스티커를 사용할때와 1번 인덱스를 사용할 때를 나눠서 DP를 구해준다.

0번의 스티커를 사용하면 맨 마지막 스티커를 사용하지 못하므로 sticker.length-1까지 순회를 한다.
1번의 스티커를 사용하면 0번의 스티커를 사용하지 못하므로 dp[0]은 0으로 설정하고 sticker.length까지 순회한다.

점화식 : 현재의 값 + 전전의 값 vs 이전의 값 을 비교하며 더 큰 값을 저장

dp[i] = max(dp[i-2] + sticker[i], dp[i-1])

그리고 스티커의 길이가 1인 경우에는 런타임오류가 뜨기 때문에 예외처리를 해준다.

코드

import java.util.*;

class Solution {
    public int solution(int sticker[]) {
        int answer = 0;
        
        if(sticker.length == 1) return sticker[0];
        
        int []dp = new int[sticker.length];
        
        //0번 인덱스부터 스티커 뜯는 경우
        //0~ sticker.length-1 까지 0번을 뜯으면 마지막부분은 사용X
        dp[0] = sticker[0];
        dp[1] = sticker[0];//3,4번째에 첫번째값을 포함시키기 위함
        for(int i = 2;i<sticker.length-1;i++)
        {
            dp[i]  = Math.max(dp[i-2]+sticker[i] , dp[i-1]);
        }
        
        //1번 인덱스부터 스티커 뜯는 경우
        //1 ~ sticker.length까지 
        int []dp1 = new int[sticker.length];
        dp1[0] = 0;
        dp1[1] = sticker[1];
        for(int i = 2;i<sticker.length;i++)
        {
            dp1[i]  = Math.max(dp1[i-2]+sticker[i] , dp1[i-1]);
        }
        
        answer = Math.max(dp[sticker.length-2],dp1[sticker.length-1]);
        return answer;
    }
}