1144. Decrease Elements To Make Array Zigzag

문제

class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        if len(nums) == 1: return 0
        
        dp = [0 for _ in range(len(nums))]
        N = len(nums)
        
        for idx in range(len(nums)):
            prevNum = nums[idx-1] if idx - 1 >= 0 else float('inf') 
            nextNum = nums[idx+1] if idx + 1 < N else float('inf')
            
            minNum = min(prevNum, nextNum) 
            
            if (prevNum <= 1000 or nextNum <= 1000) and minNum > nums[idx]:
                dp[idx] = dp[idx-2] if idx - 2 >= 0 else 0
            else:
                dp[idx] = dp[idx-2] + nums[idx] - (minNum - 1) if idx - 2 >= 0 else nums[idx] - (minNum - 1) 
        
        return min(dp[-1], dp[-2])

풀이 방법

1. 일단 숫자를 움직일 때 숫자를 작게 하는 방법 밖에 없다는 사실을 잊으면 안된다.

2. 각 인덱스의 값이 근접한 두 값보다 작게 만드는 방식으로 알고리즘을 구현하였습니다.

   1. 홀수번째 index가 근접하는 숫자보다 작은 경우
   2. 짝수번째 index가 근접하는 숫자보다 작은 경우

   두가지 경우의 수를 나누어서 계산해야 하므로 각 dp에 값을 저장할때 index-2자리의 값을 이용하여 현재 index값을 결정합니다.

3. nums의 길이가 1인 경우는 항상 0을 리턴합니다.

4. 그렇기 않을 경우 dp[-1]과 dp[-2]중에 작은 값을 리턴하면 됩니다.