[leetcode] House Robber - Python

문제링크

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제풀이

 

0과1을 초기memo로 지정해주고 이웃되지 않으면 되니까 -2 step만 확인해서 더해주면 되겠다고 생각하였습니다.

 

class Solution:
    def rob(self, nums: List[int]) -> int:
        # step이 2밖에없다.
        memo = {}
        if len(nums) == 1:
            return nums[0]

        memo[0] = nums[0]
        memo[1] = nums[1]

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

        return max(memo[len(nums) - 1], memo[len(nums) - 2])

 

이렇게하니 

[2, 1, 1, 2] 와 같이 처음과 마지막에 값을 더한 값 즉 세칸 합친경우도 있고 더한 경우들도 있었습니다.

 

다시 문제를 접근하였습니다.

 

위의 예제로 문제풀이를 해보겠습니다.

해당 문제는 ac, ace, ae 의 조합은 가능합니다.

하지만 ab, abd, acd 등 연속된 조합은 불가합니다.

 

따라서 동적계획법으로 i-2 + i , i-1을 비교하여 i를 업데이트 해주었습니다.

 

처음에 i가 1일때는 0 과 1을 비교합니다

index 0의 값이 2로 index1보다 크니까 index1를 2로 변경해줍니다

[2,2,1,2] 현재상태

 

2부터 i-2 + i, 와 i-1를 비교해줍니다

 

index2일때

i-2 + i = 2 + 1 =3

i-1 = 2

 

3으로 업데이트 해줍니다

현재상태 [2,2,3,2]

 

마지막으로 3번 index일때 비교해줍니다.

i-2 + i = 2 + 2 = 4

i-1 = 3

현재상태[2,2,3,4]

마지막 index의 값을 return 해줍니다

 

풀이코드

 

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        s = [nums[i] for i in range(len(nums))]
        
        for i in range(1, len(nums)):
            if i ==1: 
                s[1] = max(s[1], s[0])
            else:
                s[i] = max(s[i-1], s[i] + s[i-2])


        return s[len(nums) - 1]