[프로그래머스/Level3] 스티커 모으기(2) (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• DP

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

 

 

 

0번째 스티커를 뗐느냐/안 뗐느냐 여부에 따라 숫자의 합을 다르게 구한다.

  1) 0번째 스티커를 뗀 경우, 1번째와 마지막 스티커는 뗄 수 없다.

// dp 배열 초기값
dp1[0] = sticker[0];
dp1[1] = sticker[0];

 

  2) 0번째 스티커를 떼지 않은 경우, 마지막을 뜯을 수 있다.

// dp 배열 초기값
dp2[0] = 0;
dp2[1] = sticker[1];

 

 

또, 특정 위치 i에서도 스티커를 뗐느냐/안 뗐느냐 여부에 따라 2가지 경우로 구분할 수 있다.

 1) 현재 위치를 뽑는 경우, dp[i-2] + sticker[i]

 2) 현재 위치를 뽑지 않는 경우, dp[i-1]

 

이렇게 구한 두 dp 배열의 마지막 값 중 더 큰 값을 정답으로 출력한다.

 

 

 

💥 유의사항

스티커가 2개 이하인 경우에 대해 따로 처리를 해줘야 한다.

총 스티커 수가 1개면 하나만 떼면 되므로 sticker[0]이 정답이고,

총 스티커 수가 2개면 둘 중 큰 거 하나만 떼면 되므로 Math.max(sticker[0], sticker[1])이 정답이다.

 

 

🔺 코드

class Solution {
    public int solution(int sticker[]) {
        int answer = 0;
        
        // 예외 처리
        if(sticker.length == 1) {
            return sticker[0];
        }
        else if(sticker.length == 2) {
            return Math.max(sticker[0], sticker[1]);
        }
        
        // 0번을 뜯는 경우 > 1번과 마지막은 뜯을 수 X.
        int[] dp1 = new int[sticker.length - 1];
        dp1[0] = sticker[0];
        dp1[1] = sticker[0];
        
        for(int i = 2 ; i < sticker.length - 1; i++) {
            dp1[i] = Math.max(dp1[i-1], dp1[i-2] + sticker[i]);
        }
        
        // 0번을 뜯지 않은 경우 > 마지막 뜯을 수 있음
        int[] dp2 = new int[sticker.length];
        dp2[0] = 0;
        dp2[1] = sticker[1];
        
        for(int i = 2 ; i < sticker.length ; i++) {
            dp2[i] = Math.max(dp2[i-1], dp2[i-2] + sticker[i]);
        }
        
        answer = Math.max(dp1[dp1.length - 1], dp2[dp2.length - 1]);
        
        return answer;
    }
}

 

 

---

💦 어려웠던 점

- 완전탐색으로 풀 생각을 했는데 다 틀려버렸다. (N이 10만이니까 10^2하면 안 될 걸 예상하고 자연스레 dp를 떠올려야 했는데)

 

 

🧐 새로 알게 된 내용

- dp를 사용할 생각!! 데이터 크기를 생각해야 한다는 걸 잊지 말자..

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

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

 

[프로그래머스] Lv 3 스티커 모으기 (2) (Java) 문제풀이 // DP, summer/winter coding(~2018)