leetcode 213. House Robber II 풀이

문제 : 원형 큐 형태의 list로 집들이 소유한 재산값이 주어질 때, 인접한 집을 동시에 털지 않으면서 최대의 이득을 취한 값을 구하라.

 

Input: nums = [2,3,2] Output: 3 Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Follow up :

 

아이디어 : 처음에는 dp list를 만들어서 visit을 확인하려했으나 의미가 없었다. 다른 사람의 풀이를 참고하여 풀었을 때, 첫번째 원소와 마지막 원소가 이어지는 부분은 slicing으로 점화식 부분은 list를 순회하며 최대값을 구하는 방식으로 구했다.

 

코드 :

 

class Solution:
    def rob(self, nums: List[int]) -> int:
        def simple_rob(num):
            rob, not_rob = 0, 0
            for n in num:
                rob, not_rob = not_rob + n, max(not_rob, rob)
            return max(rob, not_rob)
        if len(nums) == 1:
            return nums[0]
        else:
            return max(simple_rob(nums[1:]), simple_rob(nums[:-1]))

 

학습 포인트 : 점화식을 구성하는 방법을 눈 여겨 볼 필요가 있다. 또한 list slicing의 유용함을 다시 한번 깨달았다.

 

출처 : leetcode.com/problems/house-robber-ii/