740. Delete and Earn
https://leetcode.com/problems/delete-and-earn/
문제
풀이(DFS)
이 문제에 핵심은 nums를 합치는 것이다. 즉
nums = [2, 2, 3, 3, 3, 4]라고 한다면 dp[2] = 2, dp[3] = 3, dp[4] = 1 바꾸면 된다.
이것을 해결하기 위해서 Counter모듈에 most_common()함수를 사용하였는데
arr = sorted(Counter(nums).most_common()) = > [(2, 2), (3, 3), (4, 1)]이 된다.
DFS 구조를 위에 같이 나타낼 수 있다. 즉 해당 숫자를 고를 때와 고르지 않을 때를 나눌 수 있고 만약 고른다면 그 다음 숫자와 비교해서 차이가 1이라면 X라고 볼 수 있다. 만약 고르지 않았을 때엔 그 다음에는 아무 제약 없이 숫자를 고를 때, 고르지 않을 때로 나눌 수 있을 것이다.
isNum변수는 숫자를 골랐을 때를 의미한다. 숫자를 골랐다면 이전값과 비교해서 차이가 1이면 고르지 않았을 때로 리턴해주고 차이가 1이 아니라면 골랐을 때, 고르지 않았을 때 경우의 수중 Max값을 리턴해준다. 또한 isNum이 False라면 숫자를 고르지 않았을 때를 의미하므로 다음번에는 아무제약없이 고를 수 있으므로 골랐을 때, 고르지 않았을 때 중 Max값을 리턴하도록 하였다.
결과(DFS)
풀이(DP)
DP로 푸는 방법으로는 유명한 알고리즘 문제인 'House Robber'문제가 있다. DP 방법도 DFS방법과 마찬가지로 arr = sorted(Counter(nums).most_common()) = > [(2, 2), (3, 3), (4, 1)]로 초기화한다.
dp테이블을 다음과 같이 나타낼 수 있는데 arr중 최소값인 2보다 1 작은 1을 추가한다.
i = 3일 때를 보면 그 전 최대값인 i = 1을 더한 값과 i = 2를 비교한다.
마찬가지로 i = 4일 때를 보면 i = 2에서 3을 띄고 i=4값을 더한값과 그 전값을 비교한다.
결과(DP)
