[LeetCode C++] 198. House Robber

⭐️ 난이도

Medium

 

---

⭐️ 문제

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

House Robber - LeetCode

당신은 프로페셔널한 도둑이다. 거리에 있는 집들을 도둑질하려고 한다. 각 집에는 일정한 양의 돈이 있다.

만일 인접한 두 개의 집이 같은 날 침입당했다면, security system에 의해 경찰에 자동으로 신고가 될 것이다.

 

각각의 집에 들어있는 돈의 양이 int형 배열 nums가 주어진다.

한 날에 경찰을 출동시키지 않으면서 얻을 수 있는 최대의 금액을 구하라.

 

단, nums의 길이는 100보다 작거나 같으며, 한 집에 들어있을 수 있는 금액의 범위는 400보다 작거나 같다.

---

⭐️ Follow-up

X

 

---

⭐️ Idea flow

문제를 보자마자 DP 문제일 것 같다! 하는 생각이 바로 들었다.

인접한 곳은 연속으로 도둑질을 할 수 없다.

그렇게 때문에 현재 집의 인덱스가 i라면, 이전에 도둑질을 할 수 있었던 집의 인덱스는 i-2, i-3, i-4...가 될 것이다.

하지만 i번째 집을 도둑질 할 때마다 i-2 ~ 0까지 제일 큰 것을 확인할 수는 없다.

 

우선 int형 배열 dp를 선언한다. dp[i]는 i번째 집 까지 도둑질을 할 수 있을 때, 가장 많이 훔칠 수 있는 돈의 양이다.

따라서 dp[i-2], dp[i-3], dp[i-4]는 i-2, i-3, i-4번째 집까지 도둑질을 할 수 있을 때 가장 많이 훔칠 수 있는 돈의 양이므로,

해당 값에는 다시 i-2번째보다 더 이전의 집들까지 고려하여 정해진 값이 들어가 있을 것이다.

 

따라서 dp[i]에는 (dp[i-2], dp[i-3], dp[i-4] 중 가장 큰 수 + i번째 집의 금액)이 들어가면 된다.

dp[i]를 갱신하면서 동시에 더 큰 값을 result에 대입한다.

그리고 마지막으로 result를 반환하면 된다.

 

---

⭐️ Code

class Solution {
public:
    int rob(vector<int>& nums) {
        int result = 0, len = nums.size();
        vector<int> dp;
        dp.assign(len + 1, 0);

        if(len == 0)    return 0;
        
        dp[1] = nums[0];
        if(len == 1)    return dp[1];
        
        dp[2] = nums[1];
        if(len == 2)    return max(dp[1], dp[2]);
        
        dp[3] = nums[2] + dp[1];
        result = max(max(dp[1], dp[2]), dp[3]);
        if(len == 3)    return result;

        for(int i = 4; i <= nums.size(); i++){
            int tmp = max(max(dp[i - 2], dp[i - 3]), dp[i - 4]);
            dp[i] = nums[i - 1] + tmp;
            result = max(result, dp[i]);
        }
        return result;
    }
};

 

 

---

⭐️ Feedback

 

1. 다른 풀이의 DP

나는 i-2 ~ i-4까지 확인을 했지만, 사실 그렇게 고려를 하지 않아도 되었다.

바로 옆에 있는 집을 도둑질하지 못하는 것이기 때문에, 경우의 수는 크게 두 가지로 나뉜다.

 

1) i-1번째 집을 도둑질 했을 때(즉, i번째 집은 도둑질하지 않았을 때)

2) i번째 집을 도둑질 했을 때 (즉, i-2번째 집 도둑질 O, i-1번째 집 도둑질 X)

 

두 가지 경우의 금액을 구하고, 그 중 더 큰 값을 dp[i]에 넣으면 된다.

마지막으로는 dp[nums.size()]를 반환하면 된다.

 

[전체 코드 보기]

class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp;
        dp.assign(nums.size() + 1, 0);

        if(len == 0)    return 0;
        dp[1] = nums[0];
        for(int i = 2; i <= len; i++){
            int not_included = dp[i - 1]; // i번째 집을 도둑질하지 않을 때
            int included = dp[i - 2] + nums[i - 1]; // i번째 집을 도둑질할때: i-2번째집까지의 최대 금액 + i번째 집의 금액
            dp[i] = max(not_included, included);
        }
        return dp[len];
    }
};

 

 

 

2. Optimized DP

int형 배열 dp 자체를 사용하지 않고도 문제를 풀 수 있었다.

int형 변수 prevByOne(dp[i-1]과 같음), prevByTwo(dp[i-2]와 같음)을 선언한다.

 

현재 값 int cur을 선언 한 후, prevByTwo + nums[i]와 prevByOne 중 더 큰 값을 대입한다.

해당 값이 i번째 집까지 도둑질이 가능할 때에 얻을 수 있는 최대의 돈을 뜻한다.

 

이후 prevByTwo = prevByOne;  prevByOne = cur;  을 통해 갱신을 해준다.

마지막으로는 prevByOne을 반환해주면 된다.

 

[전체 코드 보기]

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1)    return nums[0];

        // 바로 전 집, 두 번째 전 집
        int prevByOne = 0, prevByTwo = 0;
        for(int i = 0; i < nums.size(); i++){
            // == dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
            int cur = max(nums[i] + prevByTwo, prevByOne);
            prevByTwo = prevByOne;
            prevByOne = cur;
        }
        
        return prevByOne;
    }
};