Leetcode - 213. House Robber II 풀이

문제

프로페셔널 도둑에게 훔칠수 있는 돈이 기록된 집의 리스트 배열이 주어진다. 집은 원형으로 배치되어있다. 따라서 배열의 맨 처음 집과 맨 마지막 집은 인접한 집이다. 인접한 두 집을 한꺼번에 훔치면 경보가 작동해 잡혀간다. 잡혀가지 않고 최대로 많이 훔칠수 있는 금액은? (인접한 집은 배열의 바로 다음요소라는 의미)

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

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.

해결 아이디어

• [1 2 3 4 5] 일때, 1과 5는 동시에 털 수 없음. 따라서 (1 2 3 4)에서의 최대값, (2 3 4 5)에서의 최대값중 큰 값이 답이 된다. 각각의 값은 198. House Robber 문제와 동일하게 해결이 가능.
• 사전에 풀어보면 좋을 유사 문제: https://velog.io/@soopsaram/Leetcode-198.-House-Robber

풀이

class Solution {
public:
    vector<int> mem;
    int max_rob(vector<int> nums, int begin, int idx) {
        if (idx < begin)
            return 0;
        if (mem[idx] != -1)
            return mem[idx];
        mem[idx] = std::max(max_rob(nums, begin, idx - 1), max_rob(nums, begin, idx - 2) + nums[idx]);
        return mem[idx];
    }
    
    int rob(vector<int>& nums) {
        if (nums.size() == 1)
            return nums[0];

        // 1 (2 3 4 5)
        mem = vector<int>(nums.size(), -1);
        int val1 = max_rob(nums, 1, nums.size() - 1);
        
        // (1 2 3 4) 5
        mem = vector<int>(nums.size(), -1);
        int val2 = max_rob(nums, 0, nums.size() - 2);
        
        return std::max(val1, val2);
    }
};