[프로그래머스 Level 3] 스티커 모으기(2)

문제

 

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.

 

 

원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.

 

예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.

 

제한 사항

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

 

---

풀이

 

Dynamic Programming 문제다. 처음 접근할 때는 단순하게 백트래킹으로 접근했다. 하지만 당연하게 시간 초과. Deque를 이용해보기도 했는데 풀리지 않았다. 결론적으로 DP 문제라고 파악했지만 아직 점화식 세우는 게 잘 안돼서 이번 문제도 다른 사람들의 풀이를 참고했다. 찾아보니까 얼마전까지 Level4 문제였나보다.

 

문제의 그림과 마찬가지로 주어지는 스티커는 배열 형태로 주어지지만, 원형이라고 생각하고 풀어야한다. 또한, 첫 번째 스티커를 먼저 뜯느냐 두 번째 스티커를 먼저 뜯느냐에 따라에 따라 마지막 범위가 바뀐다.

 

 

첫 번째 스티커를 먼저 뜯는 경우 - A

두 번째 스티커와 마지막 스티커가 함께 찢긴다.

두 번째 스티커를 먼저 뜯는 경우 - B

 

첫 번째 스티커와 세 번째 스티커가 함께 찢긴다.

 

A케이스에서 두 번째 스티커와 마지막 스티커는 찢겨나가기 때문에 없다고 생각한다. 그렇다면 첫 번째 스티커와 세 번째 스티커부터 마지막 바로 전 스티커까지가 A케이스에서 구해야 하는 범위가 된다.

 

B케이스에서 첫 번째 스티커와 세 번째 스티커가 찢겨나가기 때문에 없다고 생각한다. 그렇다면 두 번째 스티커와 네 번째 스티커 부터 마지막 스티커까지가 B케이스에서 구해야하는 범위가 된다.

 

 

그렇다면 어떻게 구해야 할까?

 

 

A케이스에서 생각해보면

• 세 번째 스티커를 뜯는 경우 : 첫 번째 스티커를 더하는 방법 밖에 없다.
  
  
• 네 번째 스티커를 뜯는 경우 : 첫 번째 + 네 번째와 세 번째 스티커를 비교해서 더 큰 방법을 선택한다.
• 다섯 번째 스티커를 뜯는 경우 : 세 번째(첫 번째 + 세 번째) + 다섯 번째와 네 번째 스티커를 비교해서 더 큰 방법을 선택한다.
• 그렇다면, n 번째 스티커를 뜯는 경우는? (n - 2) 번째 + n 번째 스티커와 (n - 1)번째 스티커를 비교해서 더 큰 방법을 선택하면 된다.
  
  

B 케이스에서도 마찬가지로 구하면 된다. 마지막으로 A케이스와 B케이스 중 더 큰 값이 답이 된다.

 

 

public class Solution {

    public int solution(int[] sticker) {
        int N = sticker.length;
        if(N == 1) return sticker[0];

        int[][] dp = new int[2][N];

        dp[0][0] = dp[0][1] = sticker[0];
        dp[1][1] = sticker[1];

        for(int i=0; i<2; i++) {
            for(int j=2; j<N-1+i; j++) {
                dp[i][j] = Math.max(dp[i][j-1], dp[i][j-2] + sticker[j]);
            }
        }

        return Math.max(dp[0][N-2], dp[1][N-1]);
    }
}