[Leetcode/Python] House Robber

Top Interview Questions 의 Easy Collection에 있는 문제입니다.         
문제는 여기서 볼 수 있습니다.

 

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems 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.

 

Example 1:

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.

Example 2:

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

 

Constraints:

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

입력으로 주어지는 nums 리스트는 빈 리스트가 아니라는 전제 하에, 동적 계획법을 사용하여 리스트 내 좌우로 인접하지 않은 요소들을 골라 합했을 때 그 값이 최대가 되는 경우를 출력하는 문제입니다.

 

Code:

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp = nums[:] # 정답 저장하는 리스트
        if len(nums) < 3: # 리스트의 길이가 2 이하라면 최댓값 원소 하나를 그대로 반환
            return max(dp)
        # 아래 for문에 idx-2 번째 dp값을 활용하는 부분이 나오므로
        # idx-2 >= 0 이 되도록, 즉 idx=2부터 계산하도록 dp[1]까지는 미리 구한다.
        # dp[n]은 nums[:n]의 범위 내에서 문제의 요구사항을 만족하는 합의 값을 저장
        # ex) nums = [2,1,2,1,3]일 때 dp[:3] = [2,2,4]
        dp[1] = max(dp[:2])
        # 이전의 최댓값과 그보다 전의 최댓값에 현재 loop의 값을 더한 것 중 더 큰 값이 dp[idx]
        for idx, v in zip(range(2,len(nums)), nums[2:]):
            dp[idx] = max(dp[idx-1], dp[idx-2] + nums[idx])
        
        return dp[-1]

 

함수 내 첫줄에서부터 for문 전까지의 과정은 base case를 초기화하는 과정이다.

그리고 for문은 본격적으로 동적 계획법을 활용해 base case로 설정하지 않은 나머지 n번째 값을 계산해나가는 과정이다.

그리고 0~n번째 값까지 고려했을 때의 최댓값을 리스트의 n번째에 저장하는 식으로 정답 리스트를 채워나간다.

마지막으로 정답 리스트의 마지막 값을 리턴한다.

 

base case는 문제마다 다를 수 있지만 for문이나 전체적인 일련의 풀이 과정은 동적 계획법 문제라면 다 비슷한 것 같다. 그냥 외우자...!