📕문제

[Leetcode] 198. House Robber

문제 설명

도둑이 훔칠 수 있는 최대 금액을 구하는 문제다.
집에 존재하는 돈의 액수는 배열의 형태로 주어지고, 연속된 두개의 집을 털게되면 경찰에게 발각된다.
예를들어 [1,2,3,1]이 주어졌을 때 훔칠 수 있는 최대 금액은 1+3으로 4가 된다.

---

📝풀이

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return max(nums)
        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]

• 집의 개수가 3개 미만이면 가장 돈이 많은 집을 털면 된다.
• 이전 계산값을 저장하기 위한 배열 memo를 만든다.
• 탐색 과정은 두가지 경우로 나뉜다.
  • 현재 집을 털지 않고 넘어간다.
  • 이전 집을 털지 않고 현재 집을 턴다.
• 두가지 경우 중 큰 값을 저장하며 탐색을 진행한다.
• 탐색이 끝나면 memo의 마지막 값이 정답이 된다.