프로그래머스 - 스티커 모으기(2) 문제 (자바)

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

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

이문제는

첫번째 스티커부터 뜯는 경우와

두번째 스티커부터 뜯는 경우의

dp를 이용해서 해결할 수 있습니다.

 

점화식은

DP[N] = MAX(DP[N-1], STICKER[N] +DP[N-2]);

 

dpOne은 첫번째 스티커부터 뜯기 때문에 

dpOne[0], dpOne[1]은 첫번째 스티커를 뜯는 경우가 됩니다.

 

dpTwo은 첫번째 스티커부터 뜯기 때문에

dpTwo[0]은 0 (첫번째 스티커를 뜯지않기 때문에)

dpTwo[1]은 두번째 스티커를 뜯는 경우가 됩니다.

 

이후 길이를 늘려가면서 해당 길이때 최대 값을 점화식으로 구하여 두 dp중 큰값을 리턴하면 되는데

큰값을 비교할때 dpOne은 len - 2를 dpTwo는 len - 1을 사용하는데

이는 스티커가 원형으로 dpOne의 경우 마지막의 경우 찢어져서 사용하지 못하기 때문입니다. 

class Solution {
    public int solution(int sticker[]) {
        int answer = 0;
        int len = sticker.length;
        
        if(len == 1) return sticker[0];
        
        int[] dpOne = new int[len];
        int[] dpTwo = new int[len];
        
        dpOne[0] = sticker[0];
        dpOne[1] = sticker[0];
        
        dpTwo[0] = 0;
        dpTwo[1] = sticker[1];
        
        for(int i = 2; i < len; i++) {
            dpOne[i] = Math.max(dpOne[i-2] + sticker[i], dpOne[i-1]);
            dpTwo[i] = Math.max(dpTwo[i-2] + sticker[i], dpTwo[i-1]);
        }
        
        return Math.max(dpOne[len - 2], dpTwo[len - 1]);
    }
}