[1스4코3파] #275. Leetcode 198. House Robber

[1스4코3파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 3명의 파이썬 개발자코딩 테스트 서막 : 1스4코3파

START :

[3코1파] 2023.01.04~ (275일차)
[4코1파] 2023.01.13~ (267일차)
[1스4코1파] 2023.04.12~ (179일차)
[1스4코2파] 2023.05.03 ~ (157일차)
[1스4코3파] 2023.10.01 ~ (5일차)

Today :

2023.10.05 [275일차]

198. House Robber

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

문제 설명

정수 배열 nums가 주어질 때 nums의 각 인덱스에 해당하는 원소는 각 집에서 소유하고 있는 돈을 나타낸다. 각 인접한 인덱스는 보안 시스템이 연결되어 있으므로, 인접한 두 집에 침입하면 경찰에 걸리게 되는데, 걸리지 않고 훔칠 수 있는 최대 돈 금액을 반환 한다.

문제 풀이 방법

전형적인 Dynamic programming 문제로, sub 문제로 나눈다.
첫 번째 집부터 끝 집 까지 하나하나 순차적으로 훔칠 수 있는 max money를 저장하기 위해서, rob1, rob2 변수를 사용하고, 끝 집 까지 이동하면서 훔칠 수 있는 돈을 tmp에 저장해서 rob1, rob2를 update 해준 후에 최종 rob2를 return함

내 코드

class Solution:
    def rob(self, nums: List[int]) -> int:
        rob1, rob2 = 0, 0

        for n in nums:
            tmp = max(n+rob1, rob2)
            rob1 = rob2
            rob2 = tmp
        
        return rob2
        
        

증빙

여담

괴도루팡