[프로그래머스 C#] Lv.3 스티커 모으기(2)

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

DP문제로, dp[i]에는 i번까지 조건을 만족하는 최대 합을 담음

https://godgjwnsgur7.tistory.com/109

[Algorithm C#] 동적 계획법(DP) / Memoization, Tabulation

점화식 : dp[i] = (dp[i - 1] < sticker[i] + dp[i - 2]) ? sticker[i] + dp[i - 2] : dp[i - 1];

 

- 현재 탐색 중인 i번쨰의 스티커를 떼는 게 이득인지 아닌지를 파악하기 위해 dp[i]는 두 가지를 비교

 -> sticker[i] + dp[i - 2] // 현재 스티커를 떼는 경우의 합

 -> dp[i - 1] // 현재 스티커를 떼지 않는 경우의 합

위 두 가지의 경우 중 더 큰 수를 dp[i]에 넣고 다음 인덱스에 대해 연산을 반복

 

첫 번째 스티커는 마지막 인덱스의 스티커에 영향을 주므로 첫 번째 스티커를 찢는 경우와 찢지 않는 경우로 나누어서 확인해야 함

+ 첫 번째 스티커를 찢지 않았다고 하여 두 번째 스티커를 반드시 찢어야 하는 것은 아님

 

즉, 위를 토대로 첫 번째 스티커를 찢는 경우와 찢지 않는 경우를 두번 연산해 최대 값을 리턴하면 됨

 

주석 참조

    using System;

    class Solution
    {
        public int solution(int[] sticker)
        {
            int answer = 0;

            // 예외처리
            if (sticker.Length == 1)
                return sticker[0];

            var dp = new int[sticker.Length]; // DP배열

            // 첫번째 스티커를 찢는 경우
            dp[0] = sticker[0];
            dp[1] = sticker[0];

            // 마지막 스티커는 사용할 수 없음
            for (int i = 2; i < dp.Length - 1; i++)
            {
                if (dp[i - 1] < sticker[i] + dp[i - 2])
                    dp[i] = sticker[i] + dp[i - 2];
                else
                    dp[i] = dp[i - 1];
            }

            answer = dp[dp.Length - 2];

            // 첫번재 스티커를 찢지 않는 경우
            dp[0] = 0;
            dp[1] = sticker[1];

            // 마지막 인덱스까지 확인
            for (int i = 2; i < dp.Length; i++)
            {
                if (dp[i - 1] < sticker[i] + dp[i - 2])
                    dp[i] = sticker[i] + dp[i - 2];
                else
                    dp[i] = dp[i - 1];
            }
            
            if (answer < dp[dp.Length - 1])
                answer = dp[dp.Length - 1];

            return answer;
        }
    }