LeetCode - 198

sorious77·2021년 12월 1일
1

LeetCode

목록 보기
5/7

198. House Robber

https://leetcode.com/problems/house-robber/

도둑이 빈집에 몰래 들어가 돈을 훔쳐서 나오려고 한다. 이때 이웃한 집에서 연속으로 돈을 훔치면 경찰에게 걸리게 된다. 경찰에게 걸리지 않고 최대로 훔칠 수 있는 돈은 얼마일까?

이 문제는 전형적인 DP 문제다. 1 ~ N번째 집까지 최적의 방법으로 돈을 훔쳐야 한다.

X번째 집에서 도둑이 할 수 있는 선택지는 두 가지이다.

돈을 훔치거나, 안 훔치거나.

마찬가지로 X-1번째 집에서도 도둑의 선택지는 두 가지이다. 나아가서 X-2, X-3, ... 1번째 집까지 모든 집에서 두 가지의 선택지를 가진다.


다시 돌아와서, X번째 집에서 돈을 훔치는 경우를 생각해보자.
X번째 집에서 돈을 훔치려면 X-1번째 집에서는 반드시 돈을 훔치지 않아야 한다.
따라서, X-1까지의 돈(X-1 제외) + X번째 집이 X번째 집에서 훔치기로 했을 때의 금액이다.

이번에는 X번째 집에서 돈을 훔치지 않는 경우를 생각해보자.
X번째 집에서 돈을 안 훔친다면, X-1번째 집에서 돈을 훔쳐야 가장 최적의 금액을 만들 수 있을 것이다.
따라서, X-1까지의 돈(X-1 포함)이 X번째 집에서 훔치지 않았을 때의 금액이다.

쉽게 이해하기 위해 X번째에서 돈을 훔쳤을 때를 sum[x][0], 훔치지 않았을 때를 sum[x][1]로 표현해보자.

sum[x][0] = sum[x-1][1] + money[x]

sum[x][1] = sum[x-1][0]

이렇게 간단하게 수식으로 표현할 수 있다.

N번째 집까지 훔칠 수 있는 최대의 돈은 sum[n][0], sum[n][1] 둘 중 더 큰 값이 된다.


class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) {
            return nums[0];
        }
        
        int length = nums.length;
        
        int [][]dp = new int[length][2];
        
        dp[0][0] = nums[0];
        dp[0][1] = 0;
        
        dp[1][0] = nums[1];
        dp[1][1] = nums[0];
        
        for(int i=2;i<length;i++){
            dp[i][0] = Math.max(dp[i - 2][0], dp[i - 1][1]) + nums[i];
            dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);
        }
        
        return Math.max(dp[length - 1][0], dp[length - 1][1]);
    }
}

https://leetcode.com/submissions/detail/595401095/
https://github.com/sorious77/LeetCode/blob/main/code/198.java

0개의 댓글