← 19주차 · DP 입문 (1차원)
보통DP

도둑질

집들이 한 줄로 늘어서 있고, 각 집에 있는 돈이 배열 nums로 주어져요. 단, 바로 이웃한 두 집을 연달아 털면 경보가 울려요. 경보 없이 훔칠 수 있는 최대 금액을 반환해요.

각 집에서 정할 것은 '턴다 / 안 턴다' 둘 중 하나예요. i번 집까지 봤을 때의 최대 금액을 dp[i]라 하면, i번 집을 털면 dp[i-2] + nums[i], 안 털면 dp[i-1]이니 둘 중 큰 값이에요.

예시

예시 1
입력
nums = [1, 2, 3, 1]
출력
4
설명
1번째와 3번째 집을 털면 1 + 3 = 4예요.
예시 2
입력
nums = [2, 7, 9, 3, 1]
출력
12
설명
9 + 3이 아니라 2 + 9 + 1 = 12가 최대예요.

제한 사항

  • 0 ≤ nums.length ≤ 100,000
  • 0 ≤ nums[i] ≤ 10,000
값 두 개만 기억하면 돼요. prev(두 칸 전까지의 최대)와 cur(한 칸 전까지의 최대)를 두고, 각 집에서 Math.max(cur, prev + 현재 집)을 새 cur로 삼아요. 다 돌면 cur이 답이에요.
javascript
function houseRobber(nums) {
  let prev = 0;
  let cur = 0;
  for (const money of nums) {
    const next = Math.max(cur, prev + money);
    prev = cur;
    cur = next;
  }
  return cur;
}
이전 문제계단 오르기
다음 문제정수 삼각형
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.