[LeetCode] Medium - 198 House Robber

▶198 - House Robber

▶문제

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.

 

▶예제

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 = [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.

 

▶풀이

이번 문제도 dp를 이용해서 푸는 문제이다.바로 이전에 나온 값을 선택하면, 경찰이 출동하기에, 그 이전의 값들 중 max를 선택해야 한다.일단 기본적으로 1과 2는 그대로 값을 가지고 가고, 나머지 뒤에 것들을 비교한다.

 

max() 함수를 이용하는데, 안에 어떤 값을 넣을지 생각하다가 dp[:i - 1]를 넣었다.그 이유는 :를 사용하면 그 값 앞에까지 선택을 하기에, 바로 직전의 값은 선택하면 안 되기에 i - 1까지 했다.

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp = [0 for _ in range(len(nums))]
        dp[0] = nums[0]
        if len(nums) != 1:
            dp[1] = nums[1]
        for i in range(2, len(nums)):
            dp[i] = max(dp[:i - 1]) + nums[i]

        return max(dp)

이렇게 푸니까 시간도 잘 나오는 거 같았다.

하지만 같은 문제를 똑같은 풀이로 여러 번 제출하면 할 때마다 시간이 달라지는 걸로 봐서는,

시간 초과로 문제풀이를 실패하는 게 아니면, 크게 의미를 두지 않아도 될 것 같다.