[LeetCode] 740번 문제를 풀어보았다. (ft. java)

2022년 03월 05일 토요일 - 어제는 미디엄인데 개어렵고 오늘은 재밌고... 참....

오늘 올려볼 문제는 740번 Delete and Earn 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

dp 문제라서 조금 어렵긴했지만 재밌었다!

입력

사진에서도 볼 수 있듯이 int 배열 하나가 입력으로 들어온다.

---

풀이 및 코드

배열에서 하나의 원소를 삭제하고 그 만큼 돈을 번다. 이 때 원소 + 1, 원소 - 1에 해당하는 모든 원소들을 지운다.

이러한 과정을 거쳤을 때 가장 많이 벌 수 있는 돈을 구하고 리턴하는 문제다.

오늘은 처음부터 정답을 생각해냈다.

뭔가 다른 방법으로 접근했을 때 예외가 많이 생기는 것을 보아하니 dp 문제인 것 같아서 dp로 접근했다.

dp에는 현재까지 가장 큰 값을 저장한다.

dp[i - 2] + arr[i] 와 dp[i] 를 비교하는데 이는 i 보다 2작은 원소를 선택하는 것이 좋은지 아니면 i 보다 1 작은 원소를 선택하는 것이 좋은지 판단하는 부분이다.

(사실 dp는 작은 입력값으로 직접 그려보면서 값이 어떻게 변하는지 확인해야 이해가 그나마 쉽다.)

이제 코드를 봐보자!

풀이코드

class Solution {
    public int deleteAndEarn(int[] nums) {
        int[] arr = new int[10005];
        int[] dp = new int[10005];

        for(int num : nums)
        {
            arr[num] += num;
        }

        dp[1] = dp[2] = arr[1];

        for(int i = 2; i <= 10000; i++)
        {
            if(dp[i - 2] + arr[i] > dp[i])
            {
                dp[i] = dp[i - 2] + arr[i];
            }
            dp[i + 1] = dp[i];
        }

        return dp[10000];
    }
}

---

제출 화면

오래만에 내 맘에드는 재밌는 문제가 나온 것 같다.

내일도 이런 문제가 나왔으면 좋겠다!

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.