LeetCode

LeetCode 198 House Robber 풀이: 두 상태를 유지하는 동적 계획법

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

인접한 집을 연속으로 털면 안 되는 제약에서 최대 금액을 구하는 문제다. 각 집을 털지 말지 선택하는 상태와 점화식을 세워야 하는 동적 계획법 문제이므로 Level 3으로 판단했다.

1. 문제 요약

nums[i]는 i번째 집에 보관된 돈이다. 인접한 두 집을 같은 밤에 털면 경보가 울리므로 연속한 집을 털 수 없다. 경보를 울리지 않으면서 훔칠 수 있는 최대 금액을 반환해야 한다.

예를 들어 nums = [1, 2, 3, 1]이면 1번과 3번 집을 털어 1 + 3 = 4가 최대다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

점화식 도출

i번째 집을 기준으로 다음 두 선택이 있다.

  • 집 i를 턴다: nums[i]에 i - 2까지의 최대 금액을 더한다.
  • 집 i를 털지 않는다: i - 1까지의 최대 금액을 그대로 가져온다.

그래서 dp[i]를 처음 i개의 집에서 얻을 수 있는 최대 금액이라고 하면 점화식은 다음과 같다.

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

기본값은 dp[0] = nums[0], dp[1] = max(nums[0], nums[1])이다.

두 상태만 유지하기

현재 값을 계산할 때 필요한 것은 바로 이전 두 값뿐이다. prev2를 dp[i - 2], prev를 dp[i - 1]로 두고 갱신하면 배열 전체를 만들지 않아도 된다.

네 번째 집은 건너뛰는 편이 낫다

nums = [1, 2, 3, 1]에서 선택은 다음처럼 비교된다.

집 번호 금액 건너뛰기 (prev) 털기 (prev2 + nums[i]) 현재 최댓값
1 1 0 1 1
2 2 1 2 2
3 3 2 4 4
4 1 4 3 4

마지막 집을 털면 바로 앞인 세 번째 집은 포기해야 해서 1 + dp[2] = 3이다. 네 번째 집을 건너뛰면 앞에서 만든 4를 유지하므로, 이 단계에서는 집을 털지 않는 쪽을 선택한다. 초기의 prev와 prev2가 모두 0인 덕분에 첫 집이나 금액이 0인 집도 별도 분기 없이 처리된다.

3. 문제 해결 코드 (Python)

class Solution:
    def rob(self, nums: list[int]) -> int:
        prev = 0
        prev2 = 0

        for money in nums:
            current = max(prev, prev2 + money)
            prev2 = prev
            prev = current

        return prev

집을 한 번씩 순회하므로 시간 복잡도는 O(n)이다. 이전 두 상태를 변수로만 저장하므로 공간 복잡도는 O(1)이다.

4. 오답 접근과 반례

큰 금액이 있는 집을 홀수·짝수 인덱스별로 모아 둘 중 큰 값을 선택하면, 인접 여부를 고려하지 않고 특정 규칙만 따르게 된다. nums = [2, 1, 1, 2]에서 짝수 합은 2 + 1 = 3, 홀수 합은 1 + 2 = 3이지만 최적해는 첫 집과 마지막 집을 터는 2 + 2 = 4다.

집을 털 때마다 무조건 두 칸 뒤로만 이동하면, 중간에 한 집을 건너뛰는 더 좋은 경우를 놓칠 수 있다. 각 위치에서 털지 않는 선택까지 함께 비교해야 한다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 인접 제한과 최소 입력을 확인할 수 있다.

solver = Solution()
assert solver.rob([1, 2, 3, 1]) == 4
assert solver.rob([2, 7, 9, 3, 1]) == 12
assert solver.rob([5]) == 5
assert solver.rob([2, 1, 1, 2]) == 4

5. 공식 예제와 추가 검증

LeetCode 공식 예제 2개를 Python 3.12.4에서 실행했고 기대값과 일치했다.

예제 기대 출력 확인 결과
[1,2,3,1] 4 통과
[2,7,9,3,1] 12 통과

추가 검증 1: 집이 하나뿐인 경우

입력: nums = [5]
기대 출력: 5
확인 결과: 통과
검증 목적: 단일 집에서 기본값 처리 확인

추가 검증 2: 집이 두 개인 경우

입력: nums = [2, 5]
기대 출력: 5
확인 결과: 통과
검증 목적: 인접한 두 집 중 하나만 선택하는지 확인

추가 검증 3: 0이 포함된 경우

입력: nums = [0, 0, 5, 0]
기대 출력: 5
확인 결과: 통과
검증 목적: 돈이 0인 집을 건너뛰는 선택 확인

추가 검증 4: 인덱스 규칙만으로는 놓치는 경우

입력: nums = [2, 1, 1, 2]
기대 출력: 4
확인 결과: 통과
검증 목적: 첫 집과 마지막 집을 함께 선택하는 최적해 확인

6. 참고 풀이 비교

  • House Robber 공식 문제는 인접한 두 집을 같은 밤에 털 수 없다는 제약과 최대 금액을 정의한다.
  • AlgoMonster의 설명은 집을 털고 두 칸 뒤로 가거나, 털지 않고 다음 집으로 가는 재귀 관계를 설명한다.

재귀에 메모이제이션을 적용해도 같은 점화식을 저장하며 O(n) 시간과 O(n) 공간으로 해결할 수 있다. 이 글에서는 배열 대신 이전 두 상태만 유지하는 상향식 방식을 선택해 공간을 O(1)로 줄였다.

마무리

House Robber는 인접 선택 금지라는 문제의 제약이 dp[i - 2]와 dp[i - 1] 두 상태로 표현되는 대표적인 동적 계획법 문제다. 집을 터는 경우와 털지 않는 경우를 매 위치에서 비교하면 최대 금액을 구할 수 있다.

#동적계획법#LeetCode#난이도 3