[DP 문제] Leetcode 740. Delete and Earn

문제

https://leetcode.com/problems/delete-and-earn/submissions/

상기 문제는 주어진 배열 하에서 특정 값을 선택시 +1/-1 값은 지우고 다시 선택하는 과정을 반복해나가면서 선택해온 값의 합을 최대화하는 문제이다.

문제풀이

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        dp=defaultdict(int,{})
        dict_num = defaultdict(int, Counter(nums))
        minVal,maxVal=min(nums),max(nums)
        for i in range(minVal,maxVal+1):
            dp[i]=max(dp[i-1],dp[i-2]+dict_num[i]*i)
        return dp[maxVal]
  
        

Lookback

1. 인접한 숫자를 제거한다는 의미를 인접한 숫자를 선택하지 않는다는 의미로 파악하면 House Robber와 유사한 문제로 보고 쉽게 해결이 가능할 듯 보인다.