문제 설명

집에 있는 돈을 훔치는데, 한 집을 도둑질 한 뒤 바로 이웃한(adjacent)한 집을 도둑질하면 보안 경보가 울리기 때문에 바로 옆에 있는 집을 도둑질 할 수 없다. nums라는 integer array의 index가 집의 위치, 값이 돈을 의미한다. 훔칠 수 있는 최대 돈의 양을 구해야 한다.

문제 출처: https://leetcode.com/problems/house-robber/description/

문제 풀이

class Solution:
    def rob(self, nums: List[int]) -> int:
    
        if len(nums) > 1: # nums의 길이가 1인 경우 nums[0] return
            nums[1] = max(nums[0], nums[1]) # nums[0], nums[1] 중 돈이 더 많은 값을 기록

            for i in range(2, len(nums)):
                nums[i] = max(nums[i] + nums[i - 2], nums[i - 1])

        return nums[-1]

index가 0일 때: nums[0]의 돈을 훔친다.
index가 1일 때: 바로 이웃한 집의 돈을 훔칠 수 없기 때문에, nums[0], nums[1] 중 더 많이 돈이 있는 곳을 훔친다.
index가 2일 때: nums[2]와 nums[0]에서 훔칠 수 있는 돈의 양과 nums[1]에서 훔칠 수 있는 돈의 양과 비교해 더 많이 훔칠 수 있는 돈의 양을 구한다. (nums[2]에서 도둑질을 한다면 보안 경보 시스템 때문에 nums[1]에서 돈을 훔칠 수 없다.)
그 후 : (nums[n]에서 훔칠 수 있는 돈과 nums[n-2]까지 훔칠 수 있는 최대 돈의 양), (nums[n-1]까지 훔칠 수 있는 최대 돈의 양)과 비교해 최대 훔칠 수 있는 돈의 양을 구한다.