[leetcode] 집 도둑

House Robber
링크텍스트

도둑이 인접한 집은 건들지 않고 털 수 있는 최대의 돈을 구하는 문제이다.
예를 들어, [2, 7, 9, 3, 1] 배열(집)이 주어졌을 때(집1,집2,...집5),
도둑이 최대로 털 수 있는 금액은 집1(2원) + 집3(9원) + 집5(1원) = 총 12원이다.
여기서 집2(7원)와 집3(9원)은 서로 인접해 있는 집이기 때문에 털 수 없다.

주어진 배열에서 털 수 있는 금액을 계속 더해나가며 최종 금액을 구할 것이다.
먼저, 첫번째로 털 집은 집1 또는 집2 중 하나여야 한다. 두 집은 인접해있기 때문에 둘 다 털 수는 없다.
집1과 집2 중 더 큰 금액을 가지고 있는 집을 턴다.

그 다음부터 배열에서 반복문을 도는데, 현재의 i번째 위치에서,
현재보다 두번째 전 집(현재 집과 인접해 있지 않은 집)까지 턴 금액과 현재 털 집의 금액을 합한 값과, 현재 바로 전에 인접해있던 집까지 턴 금액과 비교하여 더 이득이 되는(큰 금액을 가질 수 있는 방향) 선택을 한다.

class Solution(object):
    def rob(self, nums):
        if len(nums) == 1: return nums[0]
        nums[1] = max(nums[0], nums[1]) # 집1 또는 집2 중 더 큰 금액의 집 선택

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