C++ 198. House Robber(Leet Code)

Leet Code_198. House Robber

Dynamic Programming

 

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

 

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

최대 많은 돈을 훔치기

​

방법

1. 인접하지 않는 위치만 접근 가능 

 

결과

최대 많은 돈을 훔치기

 

통과한 코드

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

DP로 짜보려고 머리를 많이 굴리면서 푼 문제

두개의 결과값을 비교해서 더 큰값을 구했다.

res = 현재위치에서 최대금액

prev_res = 이전 위치에서 최대 금액

인접하면 안되기 때문에 rev_res는 res를 구한 후 갱신해 주었다.(여기가 엄청 헷갈려서 오래걸림)