[프로그래머스, 12971] 스티커 모으기(2) (java)

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

프로그래머스

728x90

---

메모리: 60.5 MB, 시간: 18.85 ms

사용 알고리즘: 다이나믹 프로그래밍

 

현재 스티커를 뜯는 경우 중 최대값(dp[i][1])과 뜯지 않는 경우 중 최대값(dp[i][0])을 담은 dp 배열을 만든다.

0번 스티커부터 차례대로 스티커를 뜯는 경우를 구해주는데,

 

현재 스티커를 뜯을 거라면 앞 스티커는 뜯지 않은 상태여야 한다.

dp[i][1] = dp[i - 1][0] + sticker[i]

 

현재 스티커를 뜯지 않을 거라면, 앞 스티커는 뜯은 상태 거나 뜯지 않은 상태거나 상관없다.

더 큰 경우를 가져온다.

dp[i][0] = Math.max(dp[i -1][0], dp[i - 1][1])

 

그런데, 0번 스티커와 마지막 스티커 또한 연결되어 있어 0번 스티커를 뜯은 상태라면 마지막 스티커를 뜯을 수 없고

0번 스티커를 뜯지 않은 상태라면 뜯던 뜯지 않던 상관없다.

따라서 0번 스티커를 뜯었는지 뜯지 않았는지 상태를 저장해 주기 위해

0번 스티커를 뜯은 경우를 저장하는 dpWith0 배열과 뜯지 않은 경우를 저장하는 dpWithout0 배열을 만들어줬다.

class Solution {
    public int solution(int sticker[]) {
        
        // 스티커 조각이 한 개라면 한 개 그대로 땜
        if(sticker.length == 1) return sticker[0];
        
        // dp[i][0] := i번째 스티커를 뜯지 않은 경우 중 최대값
        // dp[i][1] := i번째 스티커를 뜯은 경우 중 최대값
        int[][] dpWith0 = new int[sticker.length][2]; // 0번 스티커를 뜯은 dp 배열
        int[][] dpWithout0 = new int[sticker.length][2]; // 0번 스티커를 뜯지 않은 dp 배열
        
        dpWith0[0][1] = sticker[0];
        for(int i = 1; i < sticker.length; i++) {
            // i번째 스티커를 뜯지 않는다면, i - 1번째 스티커는 뜯던 뜯지 않던 상관없음
            dpWith0[i][0] = Math.max(dpWith0[i - 1][0], dpWith0[i - 1][1]);
            dpWithout0[i][0] = Math.max(dpWithout0[i - 1][0], dpWithout0[i - 1][1]);
            
            // i번째 스티커를 뜯는다면, i -1번째 스티커는 함께 뜯을 수 없음
            dpWith0[i][1] = dpWith0[i - 1][0] + sticker[i];
            dpWithout0[i][1] = dpWithout0[i - 1][0] + sticker[i];
        }
        
        // 0번째 스티커와 n번째 스티커를 한 번에 땐 경우 빼고 최대값 구하기
        int answer = Math.max(dpWith0[sticker.length - 1][0], dpWithout0[sticker.length - 1][0]);
        answer = Math.max(answer, dpWithout0[sticker.length - 1][1]);

        return answer;
    }
}