198. House Robber

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

House Robber - LeetCode

강도가 밤사이에 거리에 있는 집을 털을 계획을 하고 있다. 인접한 두 집을 훔치게 되면 자동으로 경찰에 연락이 감으로 인접하지 않은 집을 털 때 가장 많은 금액을 출력하여라.

 

아무 생각 없이 푼 코드

인접하지만 않게 푼 코드. 역시 무엇인가 놓치는 게 있다 아래 코드는 틀렸다.

 

class Solution {
public:
    int rob(vector<int>& nums) {
        
        int sol1 = 0;
        int sol2 = 0;
        
        for(int i=0; i<nums.size(); i++) {
            if(i&1){
                sol1 += nums[i];
            }
            else {
                sol2 += nums[i];
            }
        }
        
        return max(sol1, sol2);
    }
};

 

DP 접근

현재 위치에서 +1, +2 칸 이동 할 수 있다.

class Solution {
public:
    int rob(vector<int>& nums) {
        
        int n=nums.size();
        if(n==0)return 0;
        if(n==1)return nums[0];
        if(n==2)return max(nums[0],nums[1]);
        int sol=0;
        for(int i=2;i<n;i++)
        {
            sol=INT_MIN;
            for(int k=0;k<i-1;k++){
                sol=max(nums[k]+nums[i],sol);
            }
            nums[i]=max(sol,nums[i-1]);
        }
        return nums[n-1];
    }
};