문제

• 두 이웃 집이 같은 밤에 도둑질 당하면 신고함
• 신고 당하지 않고 털 수 있는 최대 금액은?

풀이

• 연속으로 두 칸을 선택할 수는 없음
• dp[i] = [max(dp[i-2])+nums[i], dp[i-1][0]]
• dp[i][0] -> 두 집 전의 max + 이번 집
• dp[i][1] -> adjecent 집

class Solution:
    def rob(self, 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)

결과