[NeetCode-LeetCode] House Robber JAVA

반응형

728x90

[NeetCode-LeetCode] House Robber - Medium

---

접근

• dp

---

풀이

집을 약탈하여 최대한 많은 돈을 모으는 문제로 배열엔 집에서 약탈할 수 있는 돈의 금액이 들어있다. 조건으로 집을 연속하여 터는 경우 경보가 울려 경찰이 오기 때문에 연속되게 약탈을 할 수는 없다.

 

dp를 사용하면 해결되는 문제이다.

    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        if (nums.length == 1) {
            return nums[0];
        }

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
        }

        return dp[nums.length - 1];
    }

집의 개수가 0개이거나 1개인 경우 처리를 해주고 dp를 통해 최댓값을 구해줬다. 현재 집을 포함할지 안 할지에 따라 현재 집까지의 최댓값이 구해진다. 현재 집을 포함하는 경우 연속된 집을 약탈할 수 없기 때문에 2칸 전의 집까지의 최댓값을 더해주고 현재 집을 포함하지 않는 경우 이전 집까지의 최댓값을 사용하는데 둘 중 큰 값으로 현재 집까지의 최댓값을 갱신한다. 

dp

---

전체 코드

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        if (nums.length == 1) {
            return nums[0];
        }

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
        }

        return dp[nums.length - 1];
    }
}