[Leetcode] 740. Delete and Earn

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

---

DP로 풀었다.

nums 배열의 최대 요소값을 구하고 이를 maxNum이라 하자.

maxNum 크기만큼의 1차원 배열 cnts를 만들고 cnts[i] = nums 요소들중 i의 개수 를 nums 배열을 탐색하며 저장한다.

maxNum 크기만큼의 1차원 배열 dp를 만들고 이는 아래의 점화식을 가진다.

dp[i] = 0 ~ i 요소들에서 포인트를 얻을 때 얻을 수 있는 최대 포인트

         = max(dp[i-1], dp[i-2] + (cnts[i] * i)) 

i-1 번째 포인트를 얻은경우 i번째 포인트는 지워지므로 얻을 수 없지만 i-2 번째 포인트를 얻은 경우 i번째 포인트도 얻을 수 있기 때문에 위와 같은 점화식이 된다.

dp 배열을 처음부터 탐색하며 차례대로 갱신했을 때 dp[maxNum]이 정답이 된다.

 

N = maxNum이라 할 때, 시간복잡도는 O(N)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/740.%20Delete%20and%20Earn.cpp