오늘도 달리는 D P ~ 🏃‍♀️

198. House Robber

description

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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

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.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

0 <= nums.length <= 100
0 <= nums[i] <= 400

Solution

code

class Solution:
    def rob(self, nums: List[int]) -> int:
        if (len(nums) == 0) : return 0
        elif (len(nums) == 1) : return nums[0]
        money = [0] * (len(nums))
        money[0] = nums[0]
        money[1] = nums[1]
        
        for i in range (2,len(nums)) :
            if (i == 2) : money[2] = nums[0] + nums[2]
            else : money[i] = max(money[i-2], money[i-3]) + nums[i]
    
        return max(money)

Logic

처음에는 홀수번째 인덱스의 합과 짝수번째 인덱스의 합으로 생각해봤다. 근데 내 전전의 친구보다 전전전의 친구가 너무 클 수도 있지 않나? 라는 생각이 들었다.

그래서 index가 0인 경우, 1인 경우는 바로 nums[i]를 넣고 2인 경우는 nums[0] + nums[2]를 넣었다. 그 외의 경우에는 이제 바로 이전인 경우는 조건에 만족하지 않아 넣을 수 없고 i-2, i-3을 비교해서 최대값을 찾도록 했다.

Runtime: 40 ms, faster than 40.28% of Python3 online submissions for House Robber.
Memory Usage: 13.7 MB, less than 83.46% of Python3 online submissions for House Robber.

문제

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