[LeetCode]House Robber

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

강도가 들키지 않고 가장 많은 돈을 훔칠수 있는 값을 구하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        for idx in range(2, len(nums)):
            if idx > 2:
                nums[idx] = max(nums[idx-2], nums[idx-3]) + nums[idx]
            else: 
                nums[idx] = nums[idx-2] + nums[idx]

        return max(nums[-1], nums[-2])

접근 방법

1. nums 리스트를 DP로 이용합니다.
2. 집의 개수가 1개이면 해당 집의 money를 리턴합니다.
3. 세번째 집인 2부터 끝까지 반복합니다.
   1. idx가 2 이면, 현재 등장한 nums에 2개 이전의 dp 값과 현재 값을 더합니다.
   2. idx가 2 초과이면, 현재 등장한 nums에는 2번째와 3번째 이전에서 더 많이 훔친 값에 현재값을 더합니다.
4. 순회를 마치고 nums DP에서 가장 끝에 있는 2개를 비교해 더 큰 값을 리턴합니다.

우선, nums 리스트 자체를 DP로 사용합니다. DP를 누적시킬때는 2개 이전의 값과 3개 이전의 값중 큰 값을 찾아 현재값과 더해서 누적합니다.

 

자세한 예시와 함께 추가로 설명해보겠습니다. a, b, c, d는 각각의 money라고 가정합니다.

 

집이 3개인 경우, nums = [a, b, c]

1. a에서는 a
2. b에서는 b
3. c에서는 a+c

위와 같이 훔칠 수 있습니다.

 

집이 4개인 경우, nums = [a, b, c, d]

1. a에서는 a
2. b에서는 b
3. c에서는 a+c
4. d에서는 a+d, b+d중 큰 것

위와 같이 훔칠 수 있습니다.

 

집이 5개인 경우, nums = [a, b, c, d, e]

1. a에서는 a
2. b에서는 b
3. c에서는 a+c
4. d에서는 a+d, b+d중 큰 것
5. e에서는 a+c+e, b+e중 큰 것

여기에서 5번째를 자세히 살펴보면 규칙을 발견할 수 있습니다. a+c+e 값에서 a+c의 값은 이미 3번에서 구했습니다. b+e 값에서 b의 값도 이미 2번에서 구했습니다.

 

따라서, 5번의 지점에서는 (3번의 누적 DP + 5번 등장값) VS (2번의 누적 DP + 5번 등장값)중 큰값을 고르는 문제가 됩니다. 이는 곧 i-2, i-3으로 일반화가 가능합니다.

이렇게 반복하면서 가장 마지막 두 요소중 큰 값을 고르면 가장 많이 훔칠 수 있는 값을 구할 수 있습니다.