198. House Robber

순서대로 나열된 집을 터는 문제다.

조건은 연속된 집을 털면 안 된다.

 

---

 

solution 1.

집을 연속되지 않게 털려면, 현재에서 1곳 또는 2곳의 집을 띄워놓고 다른 집을 털러 갈 수 있다.

타뷸레이션을 활용한다.

 

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

        dic = collections.OrderedDict()
        dic[0] = nums[0]
        dic[1] = max(nums[1], dic[0])
        
        for i in range(2, len(nums)):
            dic[i] = max(dic[i-1], dic[i-2] + nums[i]) 
        
        return dic[len(nums)-1]

 

집이 하나도 없을 경우와 집이 두곳만 있을 경우를 생각하지 못 했다.

따라서 집이 하나도 없을 경우, 한 곳도 털지 못 했으므로 0을 리턴하고 털 집이 두곳이면 그중에서 가장 큰 곳을 골라서 털면 된다.