[Programmers]LV.3 스티커 모으기(2)

 

---

📝 기본 아이디어

제한 사항

• sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.
• sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.
• 원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.

제한 사항을 보면 배열이 10만 이하로 완전 탐색이나, DFS, BFS는 좋지 않습니다.

그렇기에 DP로 풀겠다고 마음먹었습니다.

 

• 기본 아이디어
  • DP로 시작 시 0번 스티커를 때면 마지막 스티커를 사용할 수 없다는 것을 처리해줘야 합니다.
  • 또한 이 로직이 진행되기 전에 길이가 1이면 먼저 리턴을 해줘야 자연스럽게 오류 없이 풀기가 가능합니다.

 

CASE 1:

14

6

5

11

3

9

2

10

 

케이스 1은 0번 스티커를 때면 마지막 인덱스를 사용 못하게 갱신합니다.

 

CASE 1:

14

6

5

11

3

9

2

10

 

케이스 2는 1번 스티커를 때서 정상적으로 진행합니다. 

 

식을 세워 보겠습니다.

 

CASE 1:

        // 첫 번째 스티커를 포함하는 경우
        int[] dp1 = new int[sticker.length];
        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]);
        }

 

CASE 2:

        // 첫 번째 스티커를 제외하는 경우
        int[] dp2 = new int[sticker.length];
        dp2[1] = sticker[1];
        for (int i = 2; i < sticker.length; i++) {
            dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + sticker[i]);
        }

 

class Solution {
    public int solution(int[] sticker) {
        if (sticker.length == 1) return sticker[0];
        
        // 첫 번째 스티커를 포함하는 경우
        int[] dp1 = new int[sticker.length];
        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]);
        }
        
        // 첫 번째 스티커를 제외하는 경우
        int[] dp2 = new int[sticker.length];
        dp2[1] = sticker[1];
        for (int i = 2; i < sticker.length; i++) {
            dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + sticker[i]);
        }
        
        // 두 경우 중 최대값을 반환
        return Math.max(dp1[sticker.length - 2], dp2[sticker.length - 1]);
    }
}