[LeetCode C++] 213. House Robber II

⭐️ 난이도

Medium

 

---

⭐️ 문제

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

House Robber II - LeetCode

당신은 거리에 있는 집들을 따라서 도둑질 할 계획을 세우고 있는 프로 도둑이다.

각 집마다 일정한 양의 돈이 있다.

모든 집은 원의 형태를 띄고 있다. 즉, 첫 번째 집의 이웃은 마지막 집이다.

인접한 집에는 모두 경비 시스템이 연결되어 있는데, 만일 인접한 두 집이 같은 날에 침입당한다면, 자동으로 경찰이 출동할 것이다.

 

각 집에 쌓여있는 돈에 대한 정보 배열 nums가 주어졌을 때, 경찰이 출동하지 않게 하면서 돈을 최대 얼마 도둑질할 수 있는지 구하시오.

 

---

⭐️ Follow-up

X

 

---

⭐️ Idea flow

 

이 문제에서 주어진 조건을 보면, 집이 원의 형태를 띄고 있다고 주어져있다.

첫 번째 집과 마지막 집이 바로 인접한 집임을 알 수 있는데, 이것이 문제를 푸는데에 가장 결정적인 포인트였다.

 

첫 번째 예시를 보면 주어진 집이 총 3개이다.

첫 번째 집을 도둑질 했으므로, 세 번째(마지막) 집을 도둑질 하지 못할 것이다.

 

그렇다면 집이 총 3개 일 때에만 이러한 제한이 걸리는걸까?

아니다. 집의 개수에 상관 없이 

1) 만일 첫 번째 집을 도둑질 했다면, 마지막 집을 도둑질 하지 못한다.

2) 만일 첫 번째 집을 도둑질하지 않았다면, 마지막 집을 도둑질 할 수 있다.

 

따라서 검사하는 범위를 두 개로 나누어서 DP를 진행하고, 두 개의 케이스 중에서 더 큰 값을 반환하면 된다.

 

 

 

---

⭐️ Code

class Solution {
public:
    int solve(vector<int>& nums, int s, int e){
        vector<int> dp(nums.size());
        dp[s] = nums[s];
        dp[s + 1] = max(nums[s], nums[s + 1]);
        
        for(int i = s + 2; i < e; i++){
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[e - 1];
    }
    
    int rob(vector<int>& nums) {
        if(nums.size() == 1)    return nums[0];
        if(nums.size() == 2)    return max(nums[0], nums[1]);
        
        return max(solve(nums, 0, nums.size() - 1), solve(nums, 1, nums.size()));
    }
};

 

 

---

⭐️ Feedback

 

검사하는 범위를 두 개로 나누어서 진행을 하면 된다는 것 까지는 생각을 하고, 시작점과 끝점을 매개변수로 전달을 했다.

하지만 내가 한 방법보다 더 효율적인 방법이 있을 것 같아 다른 사람들의 코드를 둘러보았다.

 

vector를 반복자를 이용하여 생성하는 방법과, int형 배열의 크기를 바로 지정하면 된다는 것을 복기할 수 있었다.

class Solution {
public:
    int solve(vector<int>& nums){
    	// int형 배열이 필요한 크기를 알고 있다면..
        int dp[nums.size()];
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        for(int i = 2; i < nums.size(); i++){
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.size() - 1];
    }
    
    int rob(vector<int>& nums) {
        int len = nums.size();
        if(len == 1)    return nums[0];
        if(len == 2)    return max(nums[0], nums[1]);
        
        // 반복자를 통해 새로운 vector에 들어갈 내용물을 정할 수 있다.
        vector<int> dp1(nums.begin(), nums.end() - 1);
        vector<int> dp2(nums.begin() + 1, nums.end());
        
        return max(solve(dp1), solve(dp2));
    }
};