213. House Robber II

House Robber II - LeetCode

양의 정수가 들어있는 1차원 배열이 주어진다.

도둑은 배열을 방문하면서 방문한 곳에 해당하는 정수만큼 돈을 훔칠 수 있다. 단 연속된 배열을 방문할 순 없고, 최소 한 칸 이상 건너서 훔칠 수 있다. 도둑이 훔칠 수 있는 최댓값을 반환하는 문제다.

 

단 주의할 점이 있다면 1차원 배열이 주어지지만 이 배열이 원형으로 되어있어 0번 인덱스와 N-1 인덱스는 인접하고 있다는 조건이 추가되었다. 그렇기 때문에 0번 인덱스와 N-1번 인덱스가 가리키는 값을 동시에 훔칠 수는 없다.

 

예시

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
because they are adjacent houses.

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Input: nums = [1,2,3]
Output: 3

1. DP (실패)

from typing import *


class Solution:
    def rob(self, nums: List[int]) -> int:
        dp = [[0] * 2 for _ in range(len(nums))]
        check = [[0] * 2 for _ in range(len(nums))]

        if len(nums) == 1:
            return nums[0]

        elif len(nums) == 2:
            return max(nums)

        dp[0][0], dp[0][1] = 0, nums[0]
        dp[1][0], dp[1][1] = nums[0], nums[1]
        check[0][1] = check[1][0] = 1

        for i in range(2, len(nums)):
            dp[i][0] = max(dp[i - 1])
            if dp[i][0] == dp[i - 1][0]:
                check[i][0] = check[i - 1][0]
            else:
                check[i][0] = check[i - 1][1]

            dp[i][1] = max(dp[i - 1][0], max(dp[i - 2]))

            if dp[i][1] == dp[i - 1][0] and check[i - 1][0]:
                check[i][1] = 1
                if i == len(nums) - 1:
                    dp[i][1] -= nums[0]
            elif dp[i][1] == dp[i - 2][0] and check[i - 2][0]:
                check[i][1] = 1
                if i == len(nums) - 1:
                    dp[i][1] -= nums[0]
            elif dp[i][1] == dp[i - 2][1] and check[i - 2][1]:
                check[i][1] = 1
                if i == len(nums) - 1:
                    dp[i][1] -= nums[0]

            dp[i][1] += nums[i]

        print(dp)
        return max(dp[-1])

dp 문제인 건 보면 알 것 같고, 점화식도 적당히 생각이 났지만 0번, N-1번 인덱스가 인접해있다는 조건을 어떻게 해결해야 할지 감이 오질 않았다. 우선 check라는 배열을 이용해 점화식을 진행하면서 현재 최댓값이 0번째 인덱스가 가리키는 값을 포함하고 있는지를 기록했고, 점화식으로 값을 업데이트할 때마다 이것을 반영해주었다.

 

마지막 방에서 dp [i][1]의 값을 업데이트할 때 check 배열 조건을 확인해 만일 True라면 nums [0]을 제외하고 nums [-1]을 더하는 식으로 작성해보았다. 하지만 예외 케이스를 통과하지 못했고, 무엇보다 이렇게 푸는 문제가 아닐 거란 생각에 위 방법은 접었다.

 

2. DP (성공)

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

        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]

        first, second = [0] * (len(nums) + 1), [0] * (len(nums) + 1)
        first[1] = nums[0]

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

        return max(first[len(nums) - 1], second[len(nums)])

first, second 배열은 첫 번째 방부터 시작했을 때 dp, 두 번째 방부터 시작했을 때 dp 배열이다.

dp 배열 사이즈를 len(nums)+1로 해서 반복문에서 예외를 편리하게 넘겼다. 점화식은 동일하다.

 

이렇게 첫 번째, 두 번째 방을 방문했을 때의 dp 배열을 따로 두고, 마지막엔 첫 번째 dp배열의 마지막 방을 방문하기 전의 최댓값과 두 번째 dp배열의 마지막 방까지 방문했을 때의 최댓값을 비교해 반환해주면 복잡한 분기문이 필요 없이 요구하는 문제 조건을 만족시킬 수 있다.

 

3. DP (수정)

from typing import *


class Solution:
    def rob(self, nums: List[int]) -> int:
        def help(nums, i, j):
            rob1, rob2 = 0, 0
            for index in range(i, j):
                rob1, rob2 = rob2 + nums[index], max(rob1, rob2)

            return max(rob1, rob2)

        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        return max(help(nums, 1, len(nums)), help(nums, 0, len(nums) - 1))

위 과정을 좀 더 우아하게 작성할 수 있다.

그러니깐 결국 dp 배열을 구하는 로직은 같은데 첫 번째 방이 포함되는 dp 배열은 nums [:len(nums)-1]를 대상으로 하고, 두 번째 방이 포함되는 dp 배열은 nums [1:len(nums)]를 대상으로 한다.

그러니깐 시작과 끝의 인덱스 값만 보내고, rob1, rob2로 index-1, index-2 시점의 최댓값을 저장하면서 업데이트하면 추가 공간도 선언할 필요 없이 문제를 해결할 수 있다.

 

LeetCode 문제집 비슷한 걸 풀고 있는데 거의 일주일 치 문제 주제가 다 DP인데 현기증 난다 ㅠ