문제

• house robber와 같은 문제
• 대신 마지막 집과 첫 집이 이웃이다

풀이

• 1번집으로 시작해서 n-1번 집으로 끝나는 경우
• 0번집으로 시작해서 n-2번 집으로 끝나는 경우

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums)>1:
            fromFirst = robbing(nums[:-1])
            toLast = robbing(nums[1:])

            return max(fromFirst, toLast)
        return nums[0]
        
        
def robbing(nums: List[int]) -> int:
    N = len(nums)
    if N > 1:
        dp = [[0,0] for _ in range(N)]
        dp[0][0] = nums[0]
        dp[1][1] = nums[0]
        dp[1][0] = nums[1]

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

        return max(dp[-1])
    else:
        return max(nums)

결과