[DP-1D][Medium] 198. House Robber

 

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. 주어진 vector nums는 각 집에 있는 돈을 의미한다. 강도가 집을 방문할때 rob 할수 있는 최대 돈의 양을 찾아라. 이때 인접한 두 집은 rob 불가능하다. 

 

 

 

Solution. 

 이전 문제와 거의 동일한 문제. 

 

 임의의 위치에서 조건을 일반화 하면, 풀이가 가능하다. 

 최대한 간결하게 해 본다. 

  

 인접해서 방문은 불가하므로, index에서 부터 출발한다고 하면,

  index+2 집 부터 어느 집이든 방문 가능하다. 

 그럼 index+2, 3, 4, 5, .. .모든 집에 대해서 접근 가능하다고 가정 할 수 있는데, 

 index+4의 집부터 다시 보면 이 집은 index+2 를 기준으로 해당 index에서 다시 index+2 임을 알 수 있다.

 

 따라서 임의의 index에서 접근 가능한 새로운 진입 index는 index+2, index+3 뿐이다.  

 

 이의 최대값을 찾는 로직으로 정리 해 본다.

 int rob_helper(vector<int>& nums, int idx)
{
    if (idx >= nums.size())
        return 0;

    int val1 = rob_helper(nums, idx + 2);
    int val2 = rob_helper(nums, idx + 3);
    return nums[idx] + max(val1, val2);
}
int rob(vector<int>& nums) 
{
	return max(rob_helper(nums, 0), rob_helper(nums, 1));
}

 

다행히 로직을 만족하고, 다만 TC 제한을 통과하지 못한다.

 

 

 

vector를 사용한 캐시를 이용한다.

 int rob_helper(vector<int>& cache, vector<int>& nums, int idx)
{
    if (idx >= nums.size())
        return 0;

    if (cache[idx] >= 0)
        return cache[idx];

    int val1 = rob_helper(cache, nums, idx + 2);
    int val2 = rob_helper(cache, nums, idx + 3);

    cache[idx] = nums[idx] + max(val1, val2);
    return cache[idx];
}

int rob(vector<int>& nums) 
{
    vector<int> cache;
    cache.resize(nums.size(), -1);
    return max(rob_helper(cache, nums, 0), rob_helper(cache, nums, 1));
}

 

잘 작동한다.

 

 

 

Note)

 혹은

이번집과 다음다음집 그리고

이번집은 건너뛰고 바로 다음집부터 계산,

이 둘 가운데 max를 구해도 답은 같을 것이다. 

 

int rob_dp(int idx, vector<int>& nums, vector<int>& vCache)
{
    if(idx >= nums.size())
        return 0;
    if(vCache[idx] >= 0)
        return vCache[idx];

    return vCache[idx] = max(nums[idx]+rob_dp(idx+2, nums, vCache), rob_dp(idx+1, nums, vCache));
}

int rob(vector<int>& nums) 
{
    vector<int> vCache;
    vCache.resize(nums.size(), -1);
    return max(rob_dp(0, nums, vCache), rob_dp(1, nums, vCache));
}

 

해당 결과.