스티커 모으기(2)

문제

문제 풀이

using System;

class Solution
{
    public int solution(int[] sticker)
    {
        // 스티커가 하나만 있을 경우
        if (sticker.Length == 1)
            return sticker[0];

        // 첫 번째 경우 (첫 번째 스티커를 포함한 경우)
        int[] dp1 = new int[sticker.Length];
        
        // 두 번째 경우 (첫 번째 스티커를 포함하지 않은 경우)
        int[] dp2 = new int[sticker.Length];

        // 첫 번째 경우 초기값 설정
        dp1[0] = sticker[0];
        dp1[1] = Math.Max(sticker[0], sticker[1]);

        // 첫 번째 경우의 dp 배열 갱신 (첫 번째 스티커를 포함한 경우)
        for (int i = 2; i < sticker.Length - 1; i++)  // 마지막 스티커는 고려하지 않음
        {
            dp1[i] = Math.Max(dp1[i - 1], dp1[i - 2] + sticker[i]);
        }

        // 두 번째 경우 초기값 설정 (첫 번째 스티커는 포함하지 않음)
        dp2[0] = 0;
        dp2[1] = sticker[1];

        // 두 번째 경우의 dp 배열 갱신 (첫 번째 스티커를 포함하지 않은 경우)
        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]);
    }
}