[pro] 프로그래머스 level3 12971 스티커 모으기2 (Java) - dp

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/12971

프로그래머스

 

[풀이]

dp[i]애는 i번째 인덱스에서의 숫자 합의 최대값을 저장한다.

 

고려해야 할 부분은 다음과 같다.

1. 스티커를 뗄 것인지, 떼지 않을 것인지?

i번째 스티커를 떼어낸다면, i-1번 스티커를 떼어낼 수 없으므로 dp[i-2]+sticker[i]가 될 것이다.

i번째 스티커를 떼어내지 않는다면, i-1번 스티커를 뗄 수 있으므로 i-1번에서의 최대값은 dp[i-1]이 될 것이다. 

이 중 최대값이 dp[i]이므로 점화식은 다음과 같다.

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

 

2. 스티커 모양이 원형이므로 첫번째 원소와 마지막 원소가 서로 연결되어 있다. 따라서 첫번째 스티커를 떼어냈다고 가정하면, 마지막 스티커는 뗄 수 없으므로 sticker.length-2까지 검사를 하고 최대값 역시 dp[sticker.length-2]가 된다.

첫번째 스티커를 떼지 않았다고 가정하면, 마지막 스티커를 뗄 수 있으므로 sticker.length-1까지 검사하고, 최대값은 dp[sticker.length-1]이 된다. 이 중 최대값이 정답이 될 것이다.

 

3. for문의 범위를 고려하여 sticker의 길이가 1이라면 sticker[0]을 반환한다. 이 코드가 없으면 test case 33에서 런타임 오류가 발생한다.

 

[코드]

 

class Solution {
    public int solution(int sticker[]) {
        int answer = 0;

        //스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 
        //dp[i]는 i번째 인덱스에서의 최대값
        
        if(sticker.length==1){
            return sticker[0];
        }
        
        //첫번째 스티커를 뗀 경우 -> 마지막 스티커 못 뗌
        int[] dp = new int[sticker.length];
        dp[0] = dp[1] = sticker[0];
        for(int i=2; i<sticker.length-1; i++){
            dp[i] = Math.max(dp[i-2]+sticker[i], dp[i-1]);
        }
        answer = dp[sticker.length-2];
        
        //첫번째 스티커를 안 뗀 경우
        dp[0] = 0;
        dp[1] = sticker[1];
        for(int i=2; i<sticker.length; i++){
            dp[i] = Math.max(dp[i-2]+sticker[i], dp[i-1]);
        }
        
        answer = Math.max(dp[sticker.length-1], answer);
        
        return answer;
    }
}