[LeetCode 해석 및 풀이] 198. House Robber(집도둑)

LeetCode 문제 해석 및 풀이 방법

문제 198. House Robber(집도둑)

난이도 : 중간🟡 바로가기

 

문제 설명

영문

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

 

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

 

한 글

당신은 거리에 있는 집을 털 계획을 세우는 전문적인 강도입니다. 각 집에는 일정 금액의 돈이 숨겨져 있으며, 당신이 각 집을 털지 못하게 막는 유일한 제약은 인접한 집에 보안 시스템이 연결되어 있고 같은 날 두 개의 인접한 집에 침입이 발생하면 자동으로 경찰에게 연락된다는 것입니다 .

 

각 집의 금액을 나타내는 정수 배열 nums 주어졌을 때, 경찰에 신고당하지 않고 하룻 밤 최대로 훔칠 수 있는 금액을 반환하세요.

 

제한조건

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

 

입출력 예

입력	출력
nums = [1,2,3,1]	4
nums = [2,7,9,3,1]	12

 

해답 및 해설

파이썬 (Python)

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

        dp = [None] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])

        return dp[-1]

우선 집이 왼쪽에 하나씩 추가된다고 생각해보자. 집이 한 채 있을 때는 한 채를 그대로 털면 되고, 두 채가 있을 때는 둘 중 금액이 높은 집을 털면 된다. 그 이후 n번째 집을 털 때를 생각해보면, 새로 추가된 n번째 집을 털고, 추가로 n-2번째 집까지에서 가장 최대 금액을 털지, 아니면 n번째 집을 터는 것을 포기하고 n-1번쨰 집까지에서 최대 금액을 털지, 두 가지 선택이 있다. 두 가지 선택 중 더 높은 금액을 털 수 있는 쪽으로 선택하면 된다. 이렇게 모든 집이 추가되었을 때를 생각하면 된다.

 

이를 코드로 나타내보면 위와 같다. dp에는 i번째 집까지 있었을 때의 털 수 있는 최대값을 저장해두고 이를 n이 될 때까지 계산해준다.

 

class Solution:
    def rob(self, nums: List[int]) -> int:
        a, b = 0, 0

        for n in nums:
            a, b = b, max(b, a + n)

        return b

위 풀이를 배열에 저장하지 않고 푼 풀이도 있었다.