동주의 세상

Clean and minimal personal blog

LeetCode 213. House Robber II 풀이, 해설, 파이썬

Posted at — Oct 12, 2021

접근

  1. 처음과 마지막이 접하기 때문에 House Robber I 과 다른 방식을 생각해야한다.
  2. 첫번째 집을 털면 마지막 집은 고려할 필요가 없다.
  3. 그래서 0, len(배열) - 1 과 1, len(배열) 로 자른 두개의 배열에 단순하게 접근하면 된다.

사고

한참 예전에 이와 비슷한 cycle 이 있는 배열 dp 문제를 풀었는데 그보다 시간이 지난 뒤에 못 풀어서 당황했던 기억이 있다. 그 당시엔 아마 배열 마지막 집 전까지 dp 업데이트 후 첫번째 집과 마지막 집 value 를 비교했던것 같은데, 위험한 접근이고 edge case 도 매우 많았을 거라 생각된다.

접근법대로 생각이 든다면 일단 dp가 만들어지고 난 후 첫번째(또는 마지막) 집을 털었는지 여부는 내가 신경쓰지 않아도 된다.

이유는 크게 두 가지 경우의 수로 나누어 생각해보면 알 수 있다.

만약 0, len(배열) - 1 의 배열에서 나온 값이 첫번째 집을 털고 나온 최적값이라면 이는 저절로 1, len(배열) 의 배열에서 나온 값 -이 dp 에서 마지막을 털었건 안 털었건 상관 없다- 과 마지막 단계에서 비교된다.

아니면 첫번째 배열에서 나온 값이 첫번째 집을 털지 않고 나온 최적값이라면 이는 두번째 집을 포함한 이후 집들 중에서 처음으로 턴 집이 나오게 된다. 결국 이 첫번째 배열의 최적값은 두번째 배열의 최적값과 1. 같거나 (최적값이 마지막에서 두번째 집을 털었을 경우), 2. 마지막 집 값만큼 더 작다(마지막에서 두번째 집을 털지 않았을 경우).

직관적으로 풀린다면 좋은 신호지만 아직 답을 써도 내일 보면 이게 왜 정확하지? 란 생각이 드는 dp 어린이기에 의심이 풀릴때까지 따져보는 것은 필요한 과정이다.

 

class Solution:
    def rob(self, nums: list[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        # if we rub, record it on first column 0
        # first exclude the last house
        dp = [[0] * 2 for _ in range(len(nums) - 1)]
        dp[0][0] = nums[0]
        for i in range(1, len(nums) - 1):
            dp[i][0] = dp[i - 1][1] + nums[i]
            dp[i][1] = max(dp[i - 1][0], dp[i - 1][1])

        temp = max(dp[len(nums) - 2])

        # then exclude the first house
        dp[0][0] = nums[1]
        for i in range(1, len(nums) - 1):
            dp[i][0] = dp[i - 1][1] + nums[i + 1]
            dp[i][1] = max(dp[i - 1][0], dp[i - 1][1])

        return max(temp, max(dp[len(nums) - 2]))