198. House Robber

난이도: 중간(Medium)

Link: LeetCode 198

풀이 날짜: 2025/10/13

 

1. 문제 이해

여러 집이 일렬로 있을 때, 도둑이 인접한 두 집을 동시에 털 수 없다는 규칙 아래에서, 훔칠 수 있는 금액의 최댓값을 구하는 문제다.

혼동하지 말아야 할 것은, 연속된 집은 털 수 없지만, 중간에 몇 집을 건너뛰어도 된다는 것이다.

 

2. 접근 아이디어 및 자료구조

이 문제는 전형적인 1D DP 구조를 가지는데, 인접한 집을 털 수 없으므로

• i번째 집을 털었을 때의 최댓값 = i-2번째까지 턴 최댓값 + 현재 집 금액 이다.
• i번째 집을 털지 않을 경우 = i-1번째까지 턴 최댓값

이 두가지 값을 비교하여 더 큰 값을 누적하는 방식으로 진행한다.

이를 점화식으로 표현하면 아래와 같지만, 

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

 

배열 대신 변수 두 개(prev1, prev2)만 사용해서 O(1) 공간으로 최적화가 가능하다.

 

3. 풀이 코드

var rob = function(nums) {
  let prev1 = 0; // i-1번째까지 최댓값
  let prev2 = 0; // i-2번째까지 최댓값

  for (const num of nums) {
    const temp = Math.max(prev1, prev2 + num); // 현재 집 털지 말지 결정
    prev2 = prev1; // 다음 스텝을 위해 이전값 업데이트
    prev1 = temp;
  }

  return prev1; // 최종 최대 금액
};

 

prev1과 prev2는 지금까지 누적한 최댓값을 저장하는 역할을 한다.

 

반복문의 temp = Math.max(prev1, prev2 + num) 코드에서 아래의

• prev1 → 바로 전 집까지 누적한 최댓값 (이번 집 털지 않는 경우)
• prev2 + num → 전전 집까지 누적한 최댓값 + 이번 집 금액 (이번 집 털 경우)

두 값 중 큰 값을 prev1에 temp를 할당하면서 누적 최댓값을 갱신한다.

즉, 반복이 끝나면 prev1에는 마지막 집까지 고려한 전체 최대 누적 금액이 저장되는 것이다.

구분	복잡도	설명
시간	O(n)	모든 집을 한 번씩 확인
공간	O(1)	두 변수만 사용

 

4. 요점 정리

• 핵심: 인접한 집을 털 수 없는 규칙 → DP 점화식
• 공간 최적화: prev1, prev2 변수만으로 1D DP 구현
• 시간 복잡도 O(n), 공간 복잡도 O(1)

 

즉, “탐색 구조는 DP, 상태 저장만 최적화”한 전형적인 1D DP 문제이다.