📕문제

[Leetcode] 213. House Robber II

문제 설명

[Leetcode] 198. House Robber에서 확장된 문제다.
도둑이 훔칠 수 있는 최대 금액을 구하는 문제다.
집에 존재하는 돈의 액수는 배열의 형태로 주어지고, 연속된 두개의 집을 털게되면 경찰에게 발각된다.
집은 원형으로 배치되어 있기 때문에 첫번째 집과 마지막 집은 이웃이 된다.

---

📝풀이

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return max(nums)
        return max(self.rob1(nums[:-1]), self.rob1(nums[1:]))
        
    
    def rob1(self, nums: List[int]) -> int:
        memo = [0] * (len(nums) + 1)
        memo[1] = nums[0]

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

        return memo[-1]

• 해당 문제는 두가지 문제로 분할하여 House Robber를 적용하면 된다.
  • 첫번째 집을 털기 : 마지막 집을 제외한 nums를 적용
  • 첫번째 집을 털지 않기 : 첫번째 집을 제외한 nums를 적용
• 두가지 경우를 이전에 해결했던 House Robber 함수에 적용시켜 큰 값을 반환한다.
  [Leetcode] 198. House Robber 풀이