동적 계획법 연습 - 집도둑(leetcode)

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

# 프로그래머스의 도둑질과 거의 똑같은 문제!(다만 프로그래머스는 원형으로 집이 배열되어 있다)

📝 배운 점

처음에 내가 풀었던 방법은 시간 효율이 안 좋았다. 그래서 discuss에 추천을 많이 받은 풀이를 찾아보았는데, 좋은 방법을 배우게 되었다.

- 내 접근: 훔치기로 확정한 집이 1번인 경우와 2번인 경우 이렇게 두 경우로 나누어서 for 문을 두 번 돌렸다. 

- 다른 분의 접근: for문을 한 번만 돌려서 해결한다! 훔칠 수 있는 최대 액수를 기록해가는 배열 맨 앞쪽에 0으로 초기화하는 빈 인덱스를 3개 추가해주면 1번을 fixed하는 경우나 2번을 fixed하는 경우가 다 고려된 동적 배열을 기록해갈 수 있기 때문이다. 여러 case 또는 복수개의 커서?흐름(?)이 필요하다고 생각되는 경우더라도, 빈 인덱스를 여러 개 만들어 둠으로써, 한 번의 for 문 안에서 다룰 수 있다는 것을 배울 수 있었다.

- for문이 두 번 도는 나의 풀이

class Solution:
    def rob(self, nums) -> int:

        # nums 원소가 한 개일 경우 그냥 해당 원소 값을 리턴
        if len(nums) == 1:
            return nums[0]

        # 빈 0번 인덱스 추가된 상태로 nums 수정
        tmp = [0]
        new_nums = tmp + nums

        # 각 칸을 끝으로 턴다고 가정할 때, 훔칠 수 있는 최대를 기록하는 배열
        dy = [0] * len(new_nums)

        answer = 0
        # i는 fixed 할 인덱스 (1번과 2번)
        for i in range(1, 3):
            dy[i] = new_nums[i]
            for j in range(i+2, len(new_nums)):
                dy[j] = max(dy[j-2], dy[j-3]) + new_nums[j]
            candidate = max(dy)
            answer = max(answer, candidate)

        return answer

- 빈 인덱스를 잘 사용한 leetcode discuss에서의 풀이

class Solution:
    def rob(self, nums: List[int]) -> int:
        nums = [0, 0, 0] + nums
        for i in range(3, len(nums)):
            b3 = nums[i-3] + nums[i]
            b2 = nums[i-2] + nums[i]
            nums[i] = max(b3, b2)
        return max(nums)