[프로그래머스] 스티커 모으기(2) - (Summer/Winter Coding(~2018))

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

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

2021-10-30

---

class Solution {
    public static int solution(int sticker[]) {
        int[][] dp = new int[sticker.length][2]; 
 
        dp[0][0] = 0; // 0 : 첫번째 스티커를 뜯지 않는 경우
        dp[0][1] = sticker[0]; // 1 : 첫번째 스티커를 뜯는 경우
 
        if(sticker.length >= 2) {
            dp[1][0] = sticker[1];
            dp[1][1] = dp[0][1];
        }
        for(int i = 2; i < sticker.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-2][0] + sticker[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-2][1] + sticker[i]);
        }
 
        if(sticker.length == 1) return sticker[0];
        return Math.max(dp[sticker.length-1][0], dp[sticker.length-2][1]);
    }
} 

 

#문제풀이

dp문제

 

dp[i][0] 에는 가장 첫번째 스티커를 뜨지 않은 경우들을 저장할 것이고, 

dp[i][1] 에는 가장 첫번째 스티커를 뜯은 경우들을 저장한다.

 

그래서 dp[i][0] 에서는

dp[i-1][0] (바로 전까지 저장한 합)과 dp[i-2][0] + sticker[i] (전전까지 저장한 합 + 지금 현재 스티커를 뜯었을 때의 합) 2개를 비교해서 더 큰 수를 저장한다.

 

마찬가지로 dp[i][1]에서는 

dp[i-1][1] (바로 전까지 저장한 합)과 dp[i-2][1] + sticker[i] (전전까지 저장한 합 + 지금 현재 스티커를 뜯었을 때의 합) 2개를 비교해서 더 큰 수를 저장한다.

 

마지막으로, 

첫번째 스티커를 뜯지 않은 경우 dp[sticker.legnth-1][0]과 첫번째 스티커를 뜯은 경우 dp[sticker.length-2][1] (마지막은 뜯을 수 없음) 두 가지를 비교해서 더 큰 값을 출력해주면 된다.

 

 

그리고 sticker의 length에 따라 조건을 나눠준 이유는 조건 상 길이(N)이 2이상이 아니라 1 이상이라고 명시했기 때문이다.

(반례로  라인 17번 지우면 33번에서 런타임 에러난다.)