[ leetcode 문제풀이 ] House Robber

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

House Robber - LeetCode

(House Robber 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< House Robber 문제 설명 >

 

House Robber 문제는 다음과 같다.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

 

(한 줄로 나열된) 집집마다 일정 금액의 돈이 숨겨져 있는데, 보안시스템이 있어 같은 날 밤 인접한 두 집에 강도가 들면 자동으로 경찰에 연락하게 된다. 주어진 각 집의 돈의 액수를 나타내는 정수 배열 nums에 대해 경찰에 알리지 않고 훔칠 수 있는 최대 금액을 리턴하여라.

 

다음 두 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 1 ≤ nums.length ≤ 100, 0 ≤ nums[i] ≤ 400 이다.

 

 

 

---

< House Robber 문제 접근(1) >

 

인접한 두 원소를 고르지 않으면서 집을 선택하는(index를 선택하는) 경우에 대한 완전 탐색을 생각해보았다. 

고르는 첫 원소로 nums[0]를 선택하면 nums[2:]에 대한 부분 문제를 호출하고, nums[1]을 선택하면 nums[3:]에 대한 부분문제를 호출한다.(nums[2]를 선택하는 경우는 nums[0], nums[2]를 선택하는 경우보다 항상 output이 작을 수 밖에 없으므로 고려하지 않음) 이후 두 결과 중 max를 리턴하면 구하고자 하는 결과 값을 얻게 된다.

이 메커니즘을 코드로 구현한 결과는 아래와 같다. (Cpp 사용)

vector<int> cache(nums.size(), -1);

int houseRobber(vector<int>& nums, int pos, vector<int>& cache){
    int n = nums.size();
    if(pos == n)		// 남은 원소가 3개일 때 경계조건
        return 0;
     
    int& ret = cache[pos];
    if(ret != -1)
        return ret;
        
    if(pos == n-1)		// 남은 원소가 1개일 때 경계조건
        return ret = nums[pos];
    if(pos == n-2)		// 남은 원소가 2개일 때 경계조건
        return ret = max(nums[pos], nums[pos+1];
        
    ret = max(nums[pos] + houseRobber(nums, pos+2, cache), nums[pos+1] + houseRobber(nums, pos+3, cache));
    return ret;
}

>> run houseRobber(nums, 0, cache);

 

위 메커니즘만 사용하면 time limit exceed가 뜨므로 cache 벡터로 메모이제이션 해준다.

(그 와중에 cache의 매개변수 선언에서 reference 처리를 안해놓고 뭐가 문제지 하고 한참을 고민했었다,,)

 

여기서 1가지 업그레이드를 진행하였다. nums 배열이 abcd ... 로 이루어져 있다고 하자.

a와 b 중 하나를 고르려 할 때 ac ... / ad... / bd ... 의 조합이 가능하다.

이때 만약 a ≥ b라면 무조건 a로 시작하는 조합이 결과값이 크다. 이를 코드에 적용하면 아래와 같다. (Cpp 사용)

 

vector<int> cache(nums.size(), -1);

int houseRobber(vector<int>& nums, int pos, vector<int>& cache){
    int n = nums.size();
    if(pos == n)		// 남은 원소가 3개일 때 경계조건
        return 0;
     
    int& ret = cache[pos];
    if(ret != -1)
        return ret;
        
    if(pos == n-1)		// 남은 원소가 1개일 때 경계조건
        return ret = nums[pos];
    if(pos == n-2)		// 남은 원소가 2개일 때 경계조건
        return ret = max(nums[pos], nums[pos+1];
    
    if(nums[pos] >= nums[pos+1])
        ret = nums[pos] + houseRobber(nums,pos+2, cache);
    else
        ret = max(nums[pos] + houseRobber(nums, pos+2, cache), 
        		nums[pos+1] + houseRobber(nums, pos+3, cache));
    return ret;
}

>> run houseRobber(nums, 0, cache);

 

이 것으로 조금 더 효율적인 알고리즘이 완성되었다. 

 

 

 

---

< House Robber 문제 접근(2) >

 

첫 번째 접근 방식은 top-down approach를 사용하였다. 그러나 코드를 다 작성하고 나서보니 왠지 코드가 지저분해 보여 bottom-up approach로도 작성해보기로 했다. (top-down approach가 확실히 생각하기에 직관적인 것에 반해 bottom-up approach는 구현하고 나서도 이거 제대로 만든 게 맞나?하고 헷갈리는 거 같다...)

 

핵심 아이디어는 i번째 원소까지의 최대 합을 누적해서 저장하는 것이다. 

구현한 코드를 먼저 살펴보자. (Cpp 사용)

int rob(vector<int>& nums) {
    if(nums.size() == 1)
        return nums[0];
    else{
        vector<int> cache(2); // 두 개의 result만 동시에 저장하고 있으면 되므로
        for(int i=0;i<nums.size();i++)
            cache[i&1] = max(cache[(i-2)&1] + nums[i], cache[(i-1)&1]);
            
        return cache[(nums.size()-1)&1];
    }
}

 

위 알고리즘의 정당성은 귀납법으로 보일 수 있다.

 

k-1번째 원소까지, k번째 원소까지의 최대 합을 안다고 하자. (cache에 저장하는 값)그럼 k+1번째 원소까지의 최대 합은 k+1번째 원소를 선택하는지 아닌지에 따라 두 가지로 경우를 나눌 수 있다.1) k+1원소를 선택하는 경우 → (k원소를 선택할 수 없으므로) k-1번째 원소까지의 최대 합 + (k+1원소)2) k+1원소를 선택하는 경우 → k번째 원소까지의 최대 합두 계산 값 중 큰 값이 바로 k+1번째 원소까지의 합이 된다.

 

한편, 1번째 원소까지의 최대 합은 nums[0], 2번째 원소까지의 최대 합은 max(nums[0], nums[1])로 알고 있으므로 귀납법이 성립함을 알 수 있다.