[leetcode 198. python] 집 도둑 (House Robber) 풀이

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

LeetCode - The World's Leading Online Programming Learning Platform

---

문제

당신은 프로페셔널한 도둑이다. 길을 따라 있는 집의 돈을 훔치려한다.

딱 한 가지 제약은, 하루동안 바로 옆에 인접(adjacent)해 있는 집의 돈을 훔칠 시, 경찰과 연결된 보안경보가 자동으로 울린다는 사실이다.

보안경보가 울리지 않게, 하루동안 훔칠 수 있는 최대의 돈을 계산해라.

---

문제 이해

문제만 봐도 재밌다. 도둑과 보안경보라니 역시 재밌어 보이는 문제가 풀기에도 재밌다. 

 

이 문제가 DP 연습하기에 좋다고 해서 미리 DP 키워드를 알고 풀긴 했지만(포스팅의 이유도 그것이다), '인접하지 않은', '최대합' 과 같은 키워드를 보고 DP의 향을 느낄 수 있었다 ..! 

 

문제에서 nums 라는 integer 배열의 index가 집의 위치(순서), 그 값은 돈을 의미한다. 기억하고 풀이로 넘어가자. 

DP 배열을 새로 만들어줘야 하나 했는데, 코드를 짜면서 보니 굳이 그럴 필요 없이 nums 배열을 갱신해 주면 됐다.

---

문제 풀이

• index가 '0'일 때:  nums[0]의 돈을 훔친다. 
• index가 '1'일 때:  nums[0],  nums[1] 을 비교해서 더 많은 돈이 있는 곳을 훔친다. (인접해있기 때문에 둘 다 훔칠 순 없다 !!!)
• index가 '2'일 때:  nums[0] + nums[2] 에서 훔칠 수 있는 돈과,  nums[1]에서 훔칠 수 있는 돈을 비교해서 더 많은 돈이 있는 곳을 훔친다!
• ...
• index가 ' i '일 때:  nums[i] + nums[i - 2] 에서 훔칠 수 있는 최대 돈의 양과, nums[i - 1] 에서 훔칠 수 있는 최대 돈의 양을 비교해서 최대로 훔칠 수 있는 돈을 구한다.

---

정답 코드

class Solution:
    def rob(self, nums: List[int]) -> int:
        l = len(nums)
        if l == 1:			# 배열 길이가 1이면, 즉 훔칠 집이 1개면 
            return nums[0]	# 그 집꺼 털기 (예외 처리)
        
        nums[1] = max(nums[0], nums[1])

        # 현재 집까지 훔친 돈과 이전 집까지 훔친 돈 중 큰 값을 비교해서 nums배열 갱신
        for i in range(2, len(nums)):
            nums[i] = max(nums[i - 2] + nums[i], nums[i - 1])

        return nums[l - 1]

---

마치며

DP의 개념만 알면 꽤 쉽게 풀린 문제였다. 너무 기쁘다!! 

하지만 오늘도 갓연아 명언으로 마무리