[LeetCode] 198. House Robber

 

https://leetcode.com/problems/house-robber/description/?envType=daily-question&envId=2024-01-21

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - House Robber

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Medium

 

 

문제

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

당신은 전문 도둑이다. 당신은 길가의 집들에서 도둑질을 하려고 한다.

각 집에는 특정한 양의 돈이 저장되어 있고, 한 집을 털면, 인접한 집은 털 수가 없다.

같은 밤동안 그 인접한 집을 털려는 순간, 경찰에게 자동으로 신고가 된다.

 

각 집의 돈의 양 nums가 주어진다. 경찰에게 들키지 않고 얻을 수 있는 최고 금액을 구하시오.

 

 

풀이

dp[i+1] = i번째 집을 방문하고 나서의 최고 액수로 설정했다.

dp[0]은 0으로, dp[1] = nums[0]으로 시작한다.

 

dp[2](i >= 1)부터는 다음의 점화식을 이용해서 최고의 값을 구한다.

dp[i+1] = max(dp[i], dp[i-1] + nums[i]) 

즉, 이번 집을 건너뛰는 경우와 이번 집을 방문하고 그 이전의 집을 방문하지 않고 이번 집을 방문하는 경우 중 더 큰 수를 저장하는 것이다.

 

dp[n]을 반환해주면 된다.

 

코드

C++

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int rob(vector<int>& nums) {
        const int n = nums.size();
        vector<int> dp(n+1, 0);
        dp[0] = 0;
        dp[1] = nums[0];

        for(int i = 1; i < n; i++) {
            dp[i+1] = max(dp[i], dp[i-1] + nums[i]);
        }

        return dp[n];
    }
};