[LeetCode 해석 및 풀이] 213. House Robber II(집도둑 2)

LeetCode 문제 해석 및 풀이 방법

문제 213. House Robber II(집도둑 2)

난이도 : 중간🟡 바로가기

 

문제 설 명

영문

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

 

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

 

한글

당신은 거리를 따라 집을 털 계획을 세우는 전문 강도입니다. 각 집에는 일정 금액의 돈이 숨겨져 있습니다. 이 장소의 모든 집은 원형으로 배열되어 있습니다. 즉, 첫 번째 집은 마지막 집의 이웃입니다. 한편, 인접한 집에는 보안 시스템이 연결되어 있으며, 같은 날 두 개의 인접한 집에 침입이 발생하면 자동으로 경찰에 연락합니다 .

 

각 집의 금액을 나타내는 정수 배열 nums 주어졌을 때, 경찰에 신고하지 않고 오늘 밤 최대로 훔칠 수 있는 금액을 반환하세요.

 

제한조건

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

 

입출력 예

입 력	출력
nums = [2,3,2]	3
nums = [1,2,3,1]	4
nums = [1,2,3]	3

 

해답 및 해설

파이썬 (Python)

class Solution:
    def rob(self, nums: List[int]) -> int:
        def robLinear(i, j):
            a, b = 0, 0

            for idx in range(i, j):
                a, b = b, max(b, a+nums[idx])
            
            return b
        
        n = len(nums)
        return max(robLinear(1, n-2)+nums[-1], robLinear(0, n-1))

집도둑 1번 문제에서 썼던 풀이를 응용해서 푼 풀이. 마지막 원소를 따로 빼놓고 생각하면 해당 문제는 인덱스 1부터 n-3번째 집까지 일직선으로 위치해있을 때 최대로 털 수 있는 금액 + 마지막 원소 금액과 0부터 n-2까지의 집까지 일직선으로 위치해있을 때 최대로 털 수 있는 금액을 비교하는 문제.