스티커 모으기(2)

문제 정보

• 프로그래머스 Lv.3
• DP
• 문제 링크

풀이

스티커를 뜯어내면 인접한 스티커는 뜯을 수 없고, 원형 배열이기 때문에 다음과 같은 두 경우로 나뉜다.

1. 첫 번째 스티커를 뜯는 경우 : 마지막 스티커는 사용할 수 없으므로, 범위는 0 ~ $n-1$
2. 첫 번째 스티커를 뜯지 않는 경우 : 범위는 1 ~ $n$

그렇기에 각각의 경우에 대해 dp를 수행해야 한다.

그리고, $i$번째 스티커를 뜯는다는 것은 $i-1$번째 스티커와 $i+1$번째 스티커는 뜯지 못한다는 것이므로, 최대값은 $i-2$번째 스티커까지 뜯었을 때의 최대값 + $i$번째 스티커의 값이 된다.

반대로, $i$번째 스티커를 뜯지 않는다는 것은 $i-1$번째 스티커와 $i+1$번째 스티커는 뜯을 수 있다는 것이므로 최대값은 $i-1$번째 스티커까지 뜯었을 때의 최대값이 된다.

$i+1$번째 스티커를 고려하지 않아도 되는 이유는 dp는 $i$를 순서대로 순회하기 때문이다. dp[i]는 ‘$i$번째 스티커까지 고려했을 때의 최대값’을 의미하며, $i+1$번째 이후는 이후 단계에서 자연스럽게 반영된다.

코드

import java.util.*;
 
class Solution {
    public int solution(int sticker[]) {
        if (sticker.length == 1)
            return sticker[0];
        
        int[] dp1 = new int[sticker.length]; // 0번 인덱스의 스티커를 뜯는 경우
        int[] dp2 = new int[sticker.length]; // 0번 인덱스의 스티커를 뜯지 않는 경우
        
        dp1[0] = sticker[0];
        dp1[1] = sticker[0];
        for (int i = 2; i < sticker.length - 1; i++) 
            dp1[i] = Math.max(dp1[i - 2] + sticker[i], dp1[i - 1]);
        
        
        dp2[0] = 0;
        dp2[1] = sticker[1];
        for (int i = 2; i < sticker.length; i++)
            dp2[i] = Math.max(dp2[i - 2] + sticker[i], dp2[i - 1]);
 
        return Math.max(dp1[sticker.length - 2], dp2[sticker.length - 1]);
    }
}