[Leetcode] 198. House Robber 문제풀이

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

House Robber - LeetCode

문제 내용

도둑질 하는데 인접한 집은 할 수 없다.

주어진 배열은 집의 돈이라고 볼 수 있고 클수록 좋다.

가장 많이 돈을 벌 수 있는 값을 찾는 문제

 

Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation:
Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

 

문제 풀이

0번째 부터 시작해서 n번째까지 하나씩 분할정복하면 된다.

마찬가지로 모든 수를 다 해봐야 되고 중복이 많기 때문에 DP를 적용하면 된다.

 

n번째 도착했을때 최대값을 생각해보자.

먼저 n번째를 선택하거나 안하거나 2개의 경우의 수를 생각할 수 있고,

그리고 인접한 경우에는 n번째를 선택할 수 없다.

또 계속 선택안하면 손해가 발생하기 때문에 n-2다음에는 필수적으로 선택해야 한다.

 

최종적으로는 3가지의 경우의 수가 발생한다.

1. n-2번째 선택x, n-1번째 선택x, n번째 선택o => rob00
2. n-2번째 선택o, n-1번째 선택x, n번째 선택o => rob01
3. n-2번째 선택x, n-1번째 선택o, n번째 선택x => rob10

마지막에 3가지 경우의 수 중에 max값을 구하면 된다.

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() < 2) {
            return *max_element(nums.begin(), nums.end());
        }
        
        int rob00 = 0;
        int rob10 = nums[0];
        int rob01 = nums[1];
        
        for (int i = 2; i < nums.size(); ++i) {
            int new00 = max(rob00, rob10);
            int new10 = rob01;
            int new01 = new00 + nums[i];
            
            rob00 = new00;
            rob10 = new10;
            rob01 = new01;
        }
        
        return max(rob00, max(rob01, rob10));
    }
};