[리트코드]740. Delete and Earn

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        if not nums:
            return 0

        freq = [0] * (max(nums)+1)
        for n in nums:
            freq[n] += n

        #print(freq)
         
        dp = [0] * len(freq)
        dp[1] = freq[1]
        for i in range(2, len(freq)):
            #print(freq[i], dp[i - 2], dp[i - 1])
            dp[i] = max(freq[i] + dp[i-2], dp[i-1])
            
        print(dp)

 

혼자서 풀어내지 못했다.

역시나 DP문제 

 

나의생각방식 

카운터로 모은다음에 곱해서 

가장 큰 값을 기준으로 양옆보다 크면 더하고 양옆 없애버리고 아니면 그 다음 큰 것 찾고

이걸 반복하려했다 

일단 구현을 하다보니 엄청 빡센거 같아서

이거 답아닌거 같은데 튀어나옴 ㅋㅋ

 

역시나 DP 문제였고 답을 보고 이해했다.

내가 푼 방식과 유사했지만 처음부터 더해서 최적의 값을 찾는 형식이었다...

이거 처음부터 더하는게 더 크다는 것이 수학적으로 뭔가 증명될것같은데.. 아시는분 댓글좀

 

아무튼 dp문제.. dp문제만 안나오면 난 뭐든지 할 수 있어 

dp 천재가 되던지 dp를 던지던지 ..

 

나중에 다시 풀어보겠다 끗.