[Python] Leetcode 213. House Robber II (Medium)

 

https://leetcode.com/problems/house-robber-ii/

House Robber II - LeetCode

 

https://nodingco.tistory.com/101?category=570522 

[Python] Leetcode 198. House Robber (Medium)

위 문제의 시리즈로 마찬가지로 DP문제입니다.

집들의 위치가 원형으로 연결되어 첫번째 집과 마지막 집이 붙어있는 형태가 되었다는 조건이 추가되었습니다.

아이디어를 떠올리기가 힘들었는데요. 

간단하게 생각하면 첫번째 집과 마지막 집은 동시에 도둑질을 할 수 없습니다.

집들을 의미하는 입력 리스트를 [첫번째 집~마지막 앞의 집]과 [두번째 집~마지막 집]으로 나누어 각각의 최댓값을 1번 문제와 같은 방식으로 구하면 둘 중에 더 큰 값이 정답이 됩니다.

 

생각해보면, [첫번째 집~마지막 앞의 집]에서 나오는 정답의 경우는 두가지로 생각해 볼 수 있습니다.

1. 첫번째 집을 도둑질 함 -> 이 경우엔 마지막 집은 당연히 털 수 없었습니다. 하지만 마지막 집을 턴 경우의 값이 더 컸을수도 있겠죠? 그 경우는 [두번째 집~마지막 집]으로 나뉜 범위에서 구한 정답이 됩니다.

2. 첫번째 집을 도둑질 하지 않음 - > 이 경우는 [두번째 집~마지막 집]으로 나눈 것에서 얻어낸 정답과 같습니다. (마지막집의 도둑질여부는 관계없습니다.)

[두번째 집~마지막 집]의 경우도 같은 방식으로 생각됩니다.

따라서 두 범위에서 문제를 풀이하면 둘 중 하나는 무조건 정답이 되게 됩니다.

 

class Solution:
    def rob(self, nums: list) -> int:
        if(len(nums) == 1):
            return nums[0]
        
        return max(self.sliceRob(nums[1:]), self.sliceRob(nums[:-1]))

    def sliceRob(self, nums: list) -> int:
        dp = [0] * (len(nums) + 1)
        dp[0] = 0
        dp[1] = nums[0]

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

        return dp[-1]


input = [[2,3,2],[1,2,3,1],[1,2,3],[1]]
for i in input:
    print(Solution().rob(i))