[리트코드 198] 인접 집을 피한 최대 금액 — 누적 동적 계획법

원제: House Robber

문제 요약

일렬로 놓인 집마다 털 수 있는 금액이 주어집니다. 인접한 두 집을 같은 밤에 털지 않으면서 얻을 수 있는 최대 금액을 반환합니다.

조건과 입출력

nums는 각 집의 금액을 담은 정수 배열입니다. 1 <= nums.length <= 100, 0 <= nums[i] <= 400이며, 인접한 집을 함께 선택할 수 없습니다.

예제와 문제 자료

예제 1: Input: nums = [1,2,3,1], Output: 4. 1번째와 3번째 집을 선택합니다. 예제 2: Input: nums = [2,7,9,3,1], Output: 12. 1번째, 3번째, 5번째 집을 선택합니다.

풀이 아이디어

코드의 dp[i]는 0번부터 i번 집까지 고려했을 때 얻을 수 있는 최대 금액입니다. i번 집을 털면 바로 앞 집은 털 수 없으므로 dp[i-2] + nums[i]가 되고, 털지 않으면 앞 구간의 최댓값 dp[i-1]을 유지합니다. 따라서 두 경우 중 큰 값을 택하면 됩니다. 이 비교는 i번 집을 포함하는 선택과 포함하지 않는 선택을 모두 살피므로, 그 구간에서 가능한 최댓값을 놓치지 않습니다.

코드의 핵심

n == 1이면 유일한 집의 금액인 nums[0]을 바로 반환합니다. 그 외에는 길이 n인 dp를 만들고 dp[0] = nums[0]으로 시작합니다.

i == 1일 때는 첫 두 집 중 하나만 고를 수 있어 dp[i] = max(dp[0], nums[1])로 초기 상태를 정합니다. continue로 다음 반복으로 넘어가므로 이 위치에서 i-2를 참조하지 않습니다.

i >= 2에서는 dp[i] = max(dp[i-2]+nums[i], dp[i-1])을 계산합니다. 마지막에는 전체 구간의 답인 dp[-1]을 반환합니다.

코드 추적 — 예제 2의 nums = [2,7,9,3,1]:

따라서 dp[-1], 즉 12를 반환합니다.

제출 코드

class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [0] * n
        dp[0] = nums[0]

        for i in range(1,n):
            if i == 1:
                dp[i] = max(dp[0],nums[1])
                continue

            dp[i] = max(dp[i-2]+nums[i],dp[i-1])

        return dp[-1]

복잡도

n = len(nums)라 할 때 반복문은 각 인덱스를 한 번씩 처리하므로 시간 복잡도는 O(n)입니다. dp 배열에 n개의 값을 저장하므로 보조 공간은 O(n)이며, 반환값은 정수 하나입니다.

복습 포인트

금액이 0인 집도 가능하지만, 코드의 선택 비교는 그대로 유효합니다. 원문 제약상 배열은 비어 있지 않으므로 dp[-1] 반환 전에 빈 배열을 따로 처리할 필요가 없습니다.

출처

문제 원문