[Leetcode] 198. House Robber (C++)

문제

198. House Robber

코드

class Solution {
public:
    int rob(vector<int>& nums) {
        int m = 0, include = 0, not_include = 0;
        
        for (auto num : nums){
            m = max(include + num, not_include);
            include = not_include;
            not_include = m;
        }
        return m;
    }
};

접근

서로 이웃한 집은 털 수가 없기 때문에 현재 방문한 집을 털 것인지 안털 것인지에 대한 구분이 필요하다고 생각했다. 그래서 i번째 집을 털기 위해서 실제로 include에 더해주고 다음 집으로 이동하면서 include 와 not_include를 바꿔야 한다고 생각했다. 그런데 이 경우 include와 not_include를 바꾸게 되면서 홀수끼리의 합, 짝수끼리의 합으로 변질되고 만다. [2, 1, 1, 2]와 같이 정답이 2이상 차이나는 위치에 있는 경우 제대로 대응할 수가 없다.

따라서 최대 값은 include와 현재 값을 더한 것과 not_include 중 큰 값으로 유지하며 include에는 not_include의 값을 할당해주어 이웃한 집을 터는 경우를 제외해준다. 마지막으로 not_include에는 유지하는 최대 값을 할당하여 향후 include가 현재 값 이전에서의 최대 값을 가질 수 있게 해준다.