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

코드 힌트

1. 문제 분석:
   • 스티커들이 원형으로 연결되어 있어서, 첫 번째 스티커를 떼면 마지막 스티커는 뗄 수 없습니다. 반대로 첫 번째 스티커를 떼지 않으면 마지막 스티커까지 떼는 것이 가능합니다.
   • 따라서 첫 번째 스티커를 떼는 경우와 떼지 않는 경우로 나누어 동적 계획법(DP)을 사용해 최댓값을 구하는 문제입니다.
2. 두 가지 케이스로 나눔:
   • 첫 번째 스티커를 떼는 경우:
     • 첫 번째 스티커를 떼었으므로 마지막 스티커는 뗄 수 없습니다.
     • 즉, 마지막 전 스티커까지 고려하여 최댓값을 구합니다.
   • 첫 번째 스티커를 떼지 않는 경우:
     • 첫 번째 스티커를 떼지 않았으므로 마지막 스티커까지 포함하여 최댓값을 구할 수 있습니다.
3. 동적 계획법(DP) 기본 아이디어:
   • DP 배열은 각 스티커를 선택할 때 얻을 수 있는 최댓값을 저장하는 배열입니다.
   • DP 배열의 인덱스 i는 스티커 배열에서 i번째 스티커를 선택할 때까지 얻을 수 있는 최대 스티커 합을 의미합니다.
   • dp[i] = max(dp[i-1], dp[i-2] + sticker[i]): i번째 스티커를 떼지 않을 경우는 이전 스티커까지의 최대 값인 dp[i-1], i번째 스티커를 뗄 경우는 dp[i-2] + sticker[i]를 계산하여 두 값 중 더 큰 값을 선택합니다.
4. 첫 번째 스티커를 떼는 경우:
   • 첫 번째 스티커를 떼었으므로, dp1[0]은 무조건 첫 번째 스티커의 값입니다.
   • dp1[1]도 첫 번째 스티커를 떼었기 때문에, 두 번째 스티커는 뗄 수 없습니다. 따라서 dp1[1] = dp1[0]입니다.
   • 이후 dp1[i]는 마지막 스티커를 제외하고, 각 스티커를 떼는 경우와 떼지 않는 경우를 비교하여 최댓값을 갱신합니다.
5. 첫 번째 스티커를 떼지 않는 경우:
   • 첫 번째 스티커를 떼지 않기 때문에, dp2[0] = 0입니다.
   • 두 번째 스티커부터 고려할 수 있으므로, dp2[1] = sticker[1]로 설정합니다.
   • 이후 마지막 스티커까지 각 스티커를 떼는 경우와 떼지 않는 경우를 비교하여 dp2[i]를 계산합니다.
6. 최종 결과:
   • 첫 번째 스티커를 떼는 경우는 마지막 전 스티커까지의 결과인 dp1[n-2]와 비교하고, 첫 번째 스티커를 떼지 않는 경우는 마지막 스티커까지의 결과인 dp2[n-1]을 비교하여 최댓값을 반환합니다.

 

 

1. dp1[n-2]인 이유 (첫 번째 스티커를 떼는 경우)

• 첫 번째 스티커를 뗐을 경우, 마지막 스티커는 뗄 수 없습니다.
• 따라서 마지막 스티커 전인 n-2번째 스티커까지 최댓값을 계산하게 됩니다.
• 즉, dp1[n-2]는 첫 번째 스티커를 뗀 상태에서 마지막 전 스티커까지의 최대값을 의미합니다.
• 마지막 스티커는 선택할 수 없으니, dp1[n-1]은 계산하지 않습니다.

2. dp2[n-1]인 이유 (첫 번째 스티커를 떼지 않는 경우)

• 첫 번째 스티커를 떼지 않으면, 마지막 스티커까지 뗄 수 있습니다.
• 따라서 마지막 스티커까지 고려한 최댓값을 구할 수 있으므로 dp2[n-1]이 사용됩니다.
• 즉, dp2[n-1]은 첫 번째 스티커를 뗄 수 없는 상황에서 마지막 스티커까지 포함한 경우의 최댓값을 의미합니다.

최종 결과 비교

• 첫 번째 스티커를 떼면 마지막 스티커는 뗄 수 없으니 dp1[n-2]까지의 최댓값을 구하고,
• 첫 번째 스티커를 떼지 않으면 마지막 스티커까지 계산하므로 dp2[n-1]까지의 최댓값을 구합니다.
• 이렇게 두 가지 경우를 비교해 더 큰 값을 결과로 반환하게 됩니다.

요약

• 첫 번째 스티커를 뗐을 때: 마지막 스티커는 뗄 수 없기 때문에 dp1[n-2]까지 고려.
• 첫 번째 스티커를 떼지 않았을 때: 마지막 스티커까지 뗄 수 있어 dp2[n-1]까지 고려.

---

정답은 더보기 클릭

class Solution {
    public int solution(int sticker[]) {
        int n = sticker.length;  // 스티커의 총 개수
        
        // 스티커가 1개일 경우, 해당 스티커 값이 답이므로 바로 반환
        if (n == 1) return sticker[0];
        
        // 두 가지 경우에 대한 dp 배열 선언
        int[] dp1 = new int[n];  // 첫 번째 스티커를 떼는 경우
        int[] dp2 = new int[n];  // 첫 번째 스티커를 떼지 않는 경우
        
        // dp1 배열 초기값 설정
        dp1[0] = sticker[0];  // 첫 번째 스티커를 떼는 경우, 첫 번째 값은 무조건 포함
        dp1[1] = sticker[0];  // 두 번째 스티커는 첫 번째를 떼면 뗄 수 없음
        
        // 첫 번째 스티커를 뗀 경우, n-1번 스티커는 떼지 않으므로 n-2까지 처리
        for (int i = 2; i < n - 1; i++) {
            dp1[i] = Math.max(dp1[i-1], dp1[i-2] + sticker[i]);  // 전 스티커를 떼는 것과 i번째 스티커를 떼는 것 중 큰 값 선택
        }
        
        // dp2 배열 초기값 설정
        dp2[0] = 0;  // 첫 번째 스티커는 떼지 않으므로 0으로 설정
        dp2[1] = sticker[1];  // 두 번째 스티커는 첫 번째를 안 뗀 상태에서 떼므로 값은 그대로
        
        // 첫 번째 스티커를 떼지 않는 경우는 마지막 스티커까지 고려 가능
        for (int i = 2; i < n; i++) {
            dp2[i] = Math.max(dp2[i-1], dp2[i-2] + sticker[i]);  // 이전 스티커를 떼거나 현재 스티커를 뗀 것 중 큰 값 선택
        }
        
        // 두 경우 중 최댓값 반환: 첫 번째 스티커를 뗀 경우 마지막 전까지 비교, 떼지 않은 경우 마지막까지 비교
        return Math.max(dp1[n-2], dp2[n-1]);
    }
}