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

1. 문제 풀이 아이디어

• 첫 번째 스티커를 선택한 경우와 두 번째 스티커를 선택한 경우로 나누어 다이나믹 프로그래밍(DP)을 적용하면 문제를 해결할 수 있다.

2. 나의 정답 코드

class Solution {
    public int solution(int sticker[]) {
        if (sticker.length == 1)
            return sticker[0];
        int[] dp = new int[sticker.length];
        dp[0] = sticker[0];
        dp[1] = sticker[0];
        for (int i = 2; i < sticker.length - 1; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + sticker[i]);
        }
        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]);
        }
        return Math.max(dp[sticker.length - 2], dp2[sticker.length - 1]);
    }
}

3. 정리

• 스티커의 길이가 1일 경우 바로 sticker[0]을 반환한다.

• 첫 번째 스티커를 선택한 경우의 다이나믹 프로그래밍을 위해 dp 배열을 초기화하고 dp[0]과 dp[1]에 sticker[0]의 값을 넣는다.

• sticker.length - 1까지 반복하며 각 위치에서 dp[i] 값을 dp[i - 1](이전 스티커를 선택하지 않은 경우)와 dp[i - 2] + sticker[i](이전 스티커를 선택했을 경우)의 최대값으로 갱신한다.

• 두 번째 스티커를 선택한 경우의 다이나믹 프로그래밍을 위해 dp2 배열을 초기화하고 dp2[0]에 0을, dp2[1]에 sticker[1]의 값을 넣는다.

• sticker.length까지 반복하며 각 위치에서 dp2[i] 값을 dp2[i - 1]과 dp2[i - 2] + sticker[i]의 최대값으로 갱신한다.

• 첫 번째 스티커를 선택한 경우의 최대값(dp[sticker.length - 2])과 두 번째 스티커를 선택한 경우의 최대값(dp2[sticker.length - 1]) 중 더 큰 값을 반환하여 문제를 해결한다.