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

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

프로그래머스

설명

이 문제는 dp로 풀 수 있다.

처음 이 문제를 풀었을 때는 현재 위치(i)에서 무조건 스티커를 떼고, i-2를 선택할지, i-3을 선택할 것인지 고민했다.

그리고 원형으로 연결된 것을 고려하여 가장 마지막에 있는 스티커와 가장 첫번째 스티커가 이어져있을 경우 제외하는 방식을 생각했다.

하지만 이렇게 풀이할 경우, 맨 앞에서부터 하니씩 확인하는 dp 문제 특성 상 가장 마지막에 있는 스티커와 첫번째 스티커가 이어져있을 경우 다른 방식으로 재확인 해야 하므로 적절치 않다.

 

그래서 다음 시도는 현재 위치(i)에서 스티커를 뗄 것인지 결정한다.

• 스티커를 뗀다면 👉 sticker[i] + dp[i-2] 
• 스티커를 떼지 않는다면 👉 dp[i-1]

중에 큰 값을 선택한다.

 

다음으로 스티커가 원형으로 연결되어 있는 것을 고려하여 가장 첫번째 원소 선택 유무를 가지고 각각 dp 배열을 만든다.

• 스티커를 선택한다면 
  dp[0] = sticker[0];
  dp[1] = sticker[0];  👉 sticker[0]이 포함되어야 하므로! dp[2], dp[3]에서 dp[1]을 찾을 때 sticker[0]을 더해야 한다.
• 스티커를 선택하지 않는다면
  dp[0] = 0;
  dp[1] = sticker[1];

이런식으로 해서 구하면 된다!

코드

class Solution {
    public int solution(int sticker[]) {
        int answer = 0;
        
        if(sticker.length == 1) {
            return sticker[0];
        }

        int[] dp1 = new int[sticker.length];
        int[] dp2 = new int[sticker.length];
        
        // 첫번째 스티커를 떼는 경우
        dp1[0] = sticker[0];
        dp1[1] = sticker[0];
        for(int i = 2; i < dp1.length - 1; i++) {
            dp1[i] = Math.max(dp1[i-1], dp1[i-2] + sticker[i]);
        }
         
        // 첫번째 스티커를 안떼는 경우
        dp2[0] = 0;
        dp2[1] = sticker[1];
        for(int i = 2; i < dp2.length; i++) {
            dp2[i] = Math.max(dp2[i-1], dp2[i-2] + sticker[i]);
        }
        
        answer = Math.max(dp1[dp1.length - 2], dp2[dp2.length - 1]);
        
        return answer;
    }
}