[파이썬] 리트코드 198. House Robber 풀이

House Robber - LeetCode

도둑이 이웃한 두 집을 연속해서 털 수 없을 때, 이익이 최대가 될 때의 값을 출력하는 문제다. 

집 1, 2, 3, 4가 이웃해 있다면, 1을 털면 2는 털 수 없는 것이다. 2를 털면 1은 털 수 없다.

집 1,2 중에서 선택이 끝나면 집 3과 4에 대해서도 동일한 과정이 반복된다.  

즉, '한 집을 털 것이냐, 털지 않고 다음 집을 털 것이냐'가 연속된 게임인 것이다.

 

따라서 

 

1. 배열의 길이만큼 0이 저장된 리스트 dp를 만들어준다. 여기에는 nums의 인덱스인 i가 주어졌을 때의 이익의 최대값을 저장한다. 

2. nums가 2보다 작다면 max(nums)가 답이 될 수밖에 없다 

3. dp[0]은 첫 번째 집과 같아질 것이고, dp[1]은 첫 번째 집과 두 번째 집 중 큰 값이 될 것이다. 

4. i가 2와 배열의 길이 사이에 있을 때 

    - dp[i]는 이번 집을 털지 않는 것(=dp[i-1])과 이번 집을 터는 것(=dp[i-2]+nums[i])중 큰 값이다 

5. 배열 dp의 마지막 값이 이익의 최대값을 나타내므로 pop해준다 

 

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp = [0 for _ in range(len(nums))]
        if not nums:
            return 0
        if len(nums)<=2 : 
            return max(nums)
        dp[0], dp[1]= nums[0], max(nums[0],nums[1])
        for i in range(2,len(nums)):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        return dp.pop()