[LeetCode] 198. House Robber [Python] 동적계획법

 

leetcode.com/problems/house-robber/

House Robber - LeetCode

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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

 

이 문제는 도둑이 보안 알람이 울리지 않는 선에서 가장 많이 털 수 있는 금액을 찾는 문제다. 보안 알람은 연속된 집을 털었을 때 울린다. 즉 ABCD의 집이 있을 때, AC, AD, BD의 조합은 알람이 울리지 않지만, AB, BC, CD, ABD 등처럼 한 집을 털고 그 바로 옆집을 연속해서 털 경우 보안 알람이 울린다. 이렇게 가장 큰 무엇인가 혹은 가장 작은 무엇인가를 찾는 문제는 다이나믹 프로그래밍이을 적용하기 좋다.

---

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

---

A (20원)	B (10원)	C (10원)	D (20원)
?	?	?	?

위의 예제에서 A 집만 있다고 가정해보자. A가 유일한 집이므로 최댓값을 내기 위해선 무조건 이 집을 털어야 한다.

A (20원)	B (10원)	C (10원)	D (20원)
20	?	?	?

A (20원) B (10원) 집이 있다고 가정해보자. A B 둘 다 털게 되면 보안시스템이 작동하게 되므로 둘 중에 하나를 골라야 한다. 둘 중 가장 많은 금액을 가지고 있는 집, A (20원)을 털면 된다. 즉 max(A, B)

A (20원)	B (10원)	C (10원)	D (20원)
20	20	?	?

A (20원) B(10원) C(10원) 이 있다고 가정해보자. 돈을 많이 털기 위해선 AC 혹은 B 중에 골라야 한다. 앞선 예제에서, AB 두 집이 있을 때, B집을 안 털고 A를 털면 더 많은 수익이 났다. 게다가 A를 털면 C도 털 수 있기 때문에 A + C 조합을 선택한다. 즉, max(A+C, B)

A (20원)	B (10원)	C (10원)	D (20원)
20	20	30	?

A (20원) B(10원) C(10원) D(20원) 이 있다고 가정해보자. 이 경우는 B와 C를 털지 않고 A + D를 터는 것이 이득이다.

A (20원)	B (10원)	C (10원)	D (20원)
20	20	30	40

이를 formula를 이용하여 나타내면, ans [i] = max(ans [i-1], ans[i-2]+nums[i])가 된다. 또한 예제에서 본대로 베이스케이스까지 함께 적어주면,

i = 0, ans[i] = nums[i]

i = 1, ans[i] = max(ans[i-1], ans [i])

ans [i] = max(ans [i-1], ans [i-2]+nums [i])

이렇게 나온다. 최종적으로 ans의 마지막 element의 값을 리턴을 해주면 문제 해결이 됐다! 2020/11/03 - [Record1] - [백준] 2839 설탕 배달 [Python] 동적계획법 에서 언급했지만, 동적 계획법(dynamic programming)을 적용할 때는 formula와 base case만 세우면 끝이다. 

해당 솔루션의 runtime complexity는 O(n), space complexity 역시 O(n)이 나온다. 코드를 보면 알겠지만, 사실 내가 필요한 어레이의 사이즈는 2개이다. space complexity를 한번 줄여볼까?

---

class Solution:
    def rob(self, nums: List[int]) -> int:
        former, later = 0, 0
        for i in nums:
            former, later = later, max(former + i, later)
        return later

---

위의 솔루션은 앞선 솔루션에서 space부분을 개선해보았다. 필요한 어레이 사이즈가 작아 변수로 변경하였다. 이 경우 runtime complexity O(n) space complexity O(1)이 나온다.