[Python] Leetcode 740. Delete and Earn (Medium)

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

Delete and Earn - LeetCode

 

 

주어진 조건에서 어떤 숫자를 선택하면 앞 뒤로 붙은 숫자들은 선택할 수 없습니다.

또 어떤 숫자를 선택하면 그 숫자는 계속 선택해도 됩니다.

 

문제의 설명만 보면 숨겨진 의도를 바로 찾기 힘들지만 생각해 보면 숫자를 연달아 선택할 수 없다는건 이전의 House Robber문제와 같은 유형이란것을 알 수 있습니다.

또 어떤 숫자를 선택하면 그 숫자에 걸린 point는 모두 획득 할 수 있기 때문에 숫자의 범위와 같은 크기의 List로 값을 압축 해 쉽게 구현 할 수 있습니다.

 

class Solution:
    def deleteAndEarn(self, nums: list) -> int:
        expectValue = [0] * 10001
        for i in nums:
            expectValue[i] += i
        
        dp = [0] * 10001
        dp[1] = expectValue[1]
        for i in range(2,10001):
            dp[i] = max(dp[i-1], dp[i-2]+expectValue[i])
        
        return dp[-1]
    

input = [[3,4,2], [2,2,3,3,3,4]]
for i in input:
    print(Solution().deleteAndEarn(i))