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

dp 문제입니다.

 

원형으로된 배열이 있고, 조건에 맞춰 원소를 뽑아 낼 때의 최댓값을 구하는 문제입니다.

하나의 원소를 뽑아낼 경우 양 쪽에 있는 원소는 뽑아낼 수 없습니다.

때문에 크게 두 가지로 구분될 수 있습니다.

1. 첫 번째 원소를 뽑는 경우(원형이기 때문에, 마지막 원소는 뽑을 수 없습니다.)
2. 첫 번째 원소를 뽑지 않는 경우

 

특정 위치를 i라고 했을 때에도 두 가지로 구분할 수 있습니다.

1. 현재 위치를 뽑는 경우 : dp[i-2] + sticker[i]
2. 현재 위치를 뽑지 않는 경우 : max(dp[i-1], dp[i-2])

 

[구현 코드]

class Solution {
    private static int[] dp1, dp2;

    public static int solution(int sticker[]) {
        int n = sticker.length;

        if(n==1) return sticker[0];

        dp1 = new int[n];
        dp2 = new int[n];

        // 처음 뜯을 때 -> 마지막 뜯을 수 없음
        dp1[0] = sticker[0];
        dp1[1] = sticker[0]; // 세,네 번째 이후에 처음의 값이 포함되게 하기 위함임
        for(int i=2; i<n-1; i++){
            dp1[i] = Math.max(dp1[i-2]+sticker[i], Math.max(dp1[i-1], dp1[i-2]));
        }

        // 처음 뜯지 않을 때 -> 마지막 뜯을 수 있음
        dp2[0] = 0;
        dp2[1] = sticker[1];
        for(int i=2; i<n; i++){
            dp2[i] = Math.max(dp2[i-2]+sticker[i], Math.max(dp2[i-1], dp2[i-2]));
        }

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