스티커 모으기(2)

문제

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

• 입력: 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 든 배열 sticker (길이 1 이상 100,000 이하)
• 출력: 스티커에 적힌 숫자의 합의 최댓값을 반환합니다.

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

풀이: 원형 배열 처리를 위한 분할 다이나믹 프로그래밍 (DP)

원형으로 연결되어 있기 때문에 첫 번째 스티커와 마지막 스티커는 인접해 있습니다. 즉, 둘을 동시에 뜯을 수는 없습니다. 이를 해결하기 위해 첫 번째 스티커의 사용 여부에 따라 두 가지 경우로 나누어 각각 DP를 수행하는 것이 핵심입니다.

• 예외 처리: 스티커가 1개밖에 없다면 인접한 것을 고려할 필요 없이 그 자체를 뜯는 것이 최대이므로 sticker[0]을 바로 반환합니다.
• 상태 정의: 1차원 배열 d1과 d2를 선언하여 각 경우에 대한 최댓값을 갱신합니다. 점화식은 dp[i] = Math.max(dp[i-1], dp[i-2] + sticker[i]) 가 됩니다. (현재 스티커를 뜯지 않고 이전까지의 최댓값을 가져갈지, 아니면 두 칸 전의 최댓값에 현재 스티커를 뜯어서 더할지 선택)
• 경우 1: 첫 번째 스티커를 뜯는 경우 (d1)
  • 첫 번째를 뜯었으므로 d1[0] = sticker[0], d1[1] = sticker[0]으로 시작합니다.
  • 마지막 스티커는 뜯을 수 없으므로 반복문은 n - 2까지만 순회합니다.
• 경우 2: 첫 번째 스티커를 뜯지 않는 경우 (d2)
  • 첫 번째를 뜯지 않았으므로 d2[0] = 0, d2[1] = sticker[1]로 시작합니다.
  • 마지막 스티커를 뜯을 수 있으므로 반복문은 끝까지(n - 1) 순회합니다.
• 결과 반환: d1의 마지막 유효 값(d1[n - 2])과 d2의 마지막 유효 값(d2[n - 1]) 중 더 큰 값을 반환합니다.

코드

class Solution {
    public int solution(int sticker[]) {
        int n = sticker.length;
        
        if (n == 1) return sticker[0];
        
        int[] d1 = new int[n];
        
        d1[0] = sticker[0];
        d1[1] = sticker[0];
        for (int i = 2; i < n - 1; i++) {
            d1[i] = Math.max(d1[i - 1], d1[i - 2] + sticker[i]);
        }
        
        int[] d2 = new int[n];
        
        d2[0] = 0;
        d2[1] = sticker[1];
        for (int i = 2; i < n; i++) {
            d2[i] = Math.max(d2[i - 1], d2[i - 2] + sticker[i]);
        }
        
        return Math.max(d1[n - 2], d2[n - 1]);
    }
}

알고리즘 분류

다이나믹 프로그래밍 (Dynamic Programming)