도둑 문제

LEETCODE - 198. House Robber

이 문제와 비슷한 문제들을 도둑 문제 유형으로 묶으려 한다.

도둑1 아이디어

이 문제에서 DP 배열은 현재 house에서 얻은 이익에 지금까지 얻은 이익의 최대값을 더한 것을 저장한다.

그리고 그 최대값을 저장하는 변수를 계속 갱신해주면서 DP를 진행한다.

class Solution:
    def rob(self, nums: List[int]) -> int:
        result = 0
        
        if len(nums) < 3:
            result = max(nums)
            
        else:
            dp = [0 for _ in range(len(nums))]
            dp[0] = nums[0]
            dp[1] = nums[1]
            previous = dp[0]
            
            for index in range(2, len(nums)):
                dp[index] = previous + nums[index]
                previous = max(previous, dp[index - 1])
            
            result = max(dp[-1], dp[-2])
        
        return result

도둑2 아이디어 (❔)

LEETCODE - 213. House Robber II
이 문제는 원형 큐처럼 집 배열이 원형으로 돼있다.
그래서 0번째 인덱스가 포함될 때와 1번째 인덱스가 포함될 때
2번을 걸쳐 DP를 진행했다.

카운터 이용

LEETCODE - 740. Delete and Earn
이 문제는 숫자들을 Counter로 묶으면 도둑 문제 아이디어로 해결할 수 있다.

기출

https://www.acmicpc.net/problem/14501
이 문제는 선택된 상담동안 진행되는 날짜는 고려하지 않게 구현하면 도둑 문제와 유형이 같다고 생각한다.

내 코드

https://www.acmicpc.net/source/48445707

🚀리팩토링(❔)

문제 상황마다 다르겠지만
도둑1 문제 같은 경우 변수 2개를 사용해서 관리할 수 있다.