[ leetcode 문제풀이 ] House Robber II

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

House Robber II - LeetCode

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

 

 

 

< House Robber II 문제 설명 >

 

House Robber II 문제는 다음과 같다.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system 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] ≤ 1000 이다.

 

 

 

---

< House Robber II 문제 접근 >

 

House Robber II 는 House Robber 문제의 응용 버전이다. 집이 원형으로 배열되어 있어 나타나는 첫 번째와 마지막 원소 간의 선택 제약을 살펴보자.

 

nums[0]을 택한다고 하면 nums[-1]은 선택이 불가하다. 마찬가지로 nums[-1]을 택한다고 하면 nums[0]은 선택이 불가하다. 

각각의 상황은 nums[0 ... n-2]와 nums[1 ... n-1] 에 대한 House Robber을 푸는 것과 동일하다. 

 

따라서, House Robber에서 사용한 알고리즘을 적용해 작성한 코드는 다음과 같다. (Cpp 사용)

(House Robber 알고리즘은 2022.01.29 - [2022 Algorithm Study(by leetcode)/Dynamic Programming] - [ leetcode 문제풀이 ] House Robber 을 참고 부탁드립니다 :D )

 

class Solution {
	int sub_rob(vector<int>& nums, int start, int end){ // nums[start ... end-1]에 대한 house robber
    	vector<int> cache(2);
        for(int i=start;i<end;i++)
    	    cache[i&1] = max(cache[(i-2)&1] + nums[i], cache[(i-1)&1]);
         
    	return cache[(end-1)&1];
	}
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1)
            return nums[0];
        else
            return max(sub_rob(nums, 1, nums.size()), sub_rob(nums, 0, nums.size()-1));
    }
};

 

house robber을 푼 상태여서 상당히 간단하게 답을 구할 수 있었다.