DDOING

Record my study

My code

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return max(nums)
        memo = [0 * _ for _ in range(len(nums))]
        memo[0],memo[1] = nums[0],nums[1]

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

1
2

Runtime : 31ms (beats 96.23%)   
Memory : 16.20MB (beats 70.68%)

풀이

  1. nums 의 길이가 3보다 작을 시에는 nums가 1개 혹은 2개일 때 이므로 배열의 최대값이 정답이 된다.
  2. memorizatoin을 사용하여 메모리를 줄이기 위해 미리 0으로 이루어진 nums길이의 배열 memo를 선언. 이 배열에는 해당 인덱스까지 더할 수 있는 가장 큰 합이 들어간다.
  3. 3번째 원소부터 비교하기 위해 nums[0],nums[1]을 미리 memo에 넣어둔다.
  4. i = 3부터, memo[i-2]까지의 max값에 nums[i]를 더한 값과, nums[i]를 비교하여 max값을 넣는다.
  5. 이를 반복하면 memo의 마지막 칸에는 nums의 마지막에서 두번째 숫자 nums[i-1]을 고려하지 않은 결과가 들어가기 때문에, memo[-1]과 memo[-2]중 큰 값을 반환한다

문제를 풀 때 DP라는 것을 아는데는 얼마 걸리지 않았지만 DP 안에서 어떤 로직을 짜야 할지 생각하는 부분이 힘들었다.
먼저 맨 처음은 위의 길이가 2 이하일때 max(nums)를 반환하는 식을 넣지 않았었는데, for문을 돌며 out of index 오류가 나서 조건을 추가해주었다. 또한 처음에는 if len(nums) < 2:였는데, 이는 길이가 1일때만 동작하지만 밑에 for문에서 range(2,2)가 되어 for문이 돌아가지 않고 return 구문에서 max로 답이 나오는 조금 이상한 코드가 되어 고쳐주었다.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) < 3: return max(nums) 

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

        return dp[-1]

같이 코드리뷰를 진행한 친구의 코드인데, 같은 memorization 방식이지만 배열에 담기는 값이 그 인덱스 위치에서 나올 수 있는 합의 최대값으로 더 명확하다.

참고