[LeetCode]House Robber II

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

강도가 들키지 않고 가장 많은 돈을 훔칠수 있는 값을 구하는 문제입니다. 단, 집이 원형으로 이어져있다고 가정합니다.

 

처음 시도한 답안

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

        dp = [0] * len(nums)
        dp[1] = nums[1]
        dp[2] = nums[2]

        dp2 = [0] * len(nums)
        dp2[0] = nums[0]
        dp2[1] = nums[1]


        for idx in range(3, len(nums)):
            dp[idx] = max(dp[idx-2], dp[idx-3]) + nums[idx]
            """
            아래와 같이 해도 무방합니다.
            if idx > 2:
                dp[idx] = max(dp[idx-2], dp[idx-3]) + nums[idx]
            else: 
                dp[idx] = dp[idx-2] + nums[idx]
            """

        for idx in range(2, len(nums)-1):
            if idx > 2:
                dp2[idx] = max(dp2[idx-2], dp2[idx-3]) + nums[idx]
            else: 
                dp2[idx] = dp2[idx-2] + nums[idx]

        return max(dp[-1], dp[-2], dp2[-2], dp2[-3])

접근 방법

1. 2개의 DP를 사용하여 풀이합니다.
2. dp는 2~n의 집만 있다고 가정합니다. dp2는 1~n-1의 집만 있다고 가정합니다.
3. 각 dp별로 순회합니다.
4. dp의 경우
   1. 2부터 집이 시작된다고 가정하기에 3부터 집의 끝까지 반복을 수행합니다.
   2. 2번째 전까지와 3번째 전까지의 값중 큰 값을 골라 현재값과 더합니다.
5. dp2의 경우
   1. 1부터 집이 시작되기에 시작은 2, n-1까지 존재하기에 집의 끝-1 까지 반복을 수행합니다.
   2. idx가 2 초과라면, 2번째 전과 3번째 전의 값중 큰 값을 골라 현재값과 더합니다.
   3. idx가 2라면, 3번째 전의 요소는 없으니 2번째 전의 요소와 현재값을 더합니다.
6. 반복을 마치고 dp, dp2에서 각 끝에서 2개의 요소를 골라 가장 큰 값을 리턴합니다.

이 문제는 이전에 풀이한 House Robber의 응용버전입니다. 집들이 서로 원형으로 이어져있다는 점이 차이점입니다.

원형으로 이어져있기 때문에 아래와 같이 2가지의 경우로 나누어 생각해볼 수 있습니다.

 

1. 1~n-1 까지만 집이 있다고 가정하는 상황. (첫번째 집을 훔친다면 마지막 집은 훔치지 못합니다.)
2. 2~n 까지만 집이 있다고 가정하는 상황. (마지막 집을 훔친다면 첫번째 집은 훔치지 못합니다.) 

따라서 이 두개의 경우를 각각 DP로 구해서 가장 큰 값을 구하면 돈을 가장 많이 훔치는 경우의 수를 파악할 수 있습니다.

두가지 경우로만 나뉘게 된다면 이전에 풀이한 House Robber 문제와 동일하게 변경이 됩니다.

 

이전에 풀이한 House Robber 문제

https://leffept.tistory.com/541