[1-DP][Medium] 213. House Robber II

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

 

주어진 정수 배열을 각 집과 그 집에서 rob 할수 있는 value라고 한다. 

이때 도둑은 인접해 있는 집은 털수가 없다. 또한 집들이 원형으로 연결되어 있다고 가정한다.

따라서 마지막 집과 첫 집은 연결되어 있다. 

 

도둑이 훔칠 수 있는 최대값을 찾아라.

 

House Robber I 문제의 변형이다. 

 

특정 위치에서 idx+2 혹은 idx+3에 접근 할 수 있다. 

다만, 0에서 시작했으면 size()-1 까지만 접근 가능하다. 

따라서 캐시 버퍼를 만들때 이 경우를 고려한다. 따라서 size() x 2의 캐시 사이즈가 필요하다.

 

또한 시작 시, 첫 집에서 시작 할 수 있고, 이때는 마지막 집은 접근 할 수 없다.

두번째, 혹은 세번째 집에서 시작 할 수 있고 이때는 마지막 집은 접근 가능하다. 

 

이를 기본으로 로직을 만든다. 

 

코드

int doRobDP(int idx, vector<int>& vCache, const vector<int>& nums, int n)
{
    if(idx >= n)
        return 0;

    int idxCache = n==nums.size()-1 ? idx : nums.size() + idx;
    if(vCache[idxCache] >= 0)
        return vCache[idxCache];

    vCache[idxCache] = nums[idx] + max(doRobDP(idx+2, vCache, nums, n), doRobDP(idx+3, vCache, nums, n));
    return vCache[idxCache];
}

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

    vector<int> vCache;
    vCache.resize(nums.size()*2, -1);

    int cost = max(doRobDP(0, vCache, nums, nums.size()-1), doRobDP(1, vCache, nums, nums.size()));
    cost = max(cost, doRobDP(2, vCache, nums, nums.size()));
    return cost;
}

 

 

 

 

결과