문제 보기 · Level 4 · 동적계획법(Dynamic Programming) · 정답률 42% · 푼 사람 11,417명 (2026-09-30 기준)1

문제

집들이 동그랗게 놓여 있고, 이웃한 두 집을 털면 경보가 울린다. 집마다 든 돈이 주어질 때 훔칠 수 있는 돈의 최댓값을 돌려준다.

  • 집 3 ~ 1,000,000개
  • 집마다 돈 0 ~ 1,000

풀이

막히면 한 단계씩 펼친다.

필요한 개념

동적 계획법: 한 줄의 집이면 “i번째 집까지 봤을 때의 최대”를 앞에서부터 채운다. 동그라미는 첫 집과 마지막 집이 이웃이라, 둘 중 하나를 빼고 두 번 푼다.

1단계 · 작은 예로 손으로 풀기

[1, 2, 3, 1]이 동그랗게 놓였다.

  • 1번째와 3번째(1 + 3 = 4), 2번째와 4번째(2 + 1 = 3)를 털 수 있다.
  • 1번째와 4번째는 동그라미라 이웃이다. 함께 털 수 없다.

답은 4다. 동그라미 조건만 없으면 한 줄 문제와 같다.

2단계 · 가장 단순한 방법과 그 속도

털 집을 모두 고르면 2ⁿ가지다. n이 100만이면 어림없다.

3단계 · 핵심 아이디어
  • 한 줄이면: dp[i] = i번째 집까지 봤을 때의 최대. i번째 집을 털면 i − 1번째는 못 털어 dp[i − 2] + (i번째 돈), 안 털면 dp[i − 1]. 둘 중 큰 쪽이다. 털면 1, 안 털면 0으로 적으면 털 계획은 이웃한 1이 없는 0·1 문자열이다. 길이 i인 이런 문자열의 수 \(a_i\)를 마지막 자리로 나눠 세면 피보나치 꼴의 선형 점화식 \(a_i = a_{i-1} + a_{i-2}\)가 나온다. dp 식은 이 덧셈을 max로 바꾸고, \(a_{i-2}\) 쪽(마지막 집을 턴 경우)에 i번째 집의 돈을 더한 것이다.
  • 동그라미: 첫 집과 마지막 집은 함께 털 수 없다. 그러니 “마지막 집을 뺀 한 줄”과 “첫 집을 뺀 한 줄” 중 하나에 답이 있다. 두 번 풀어 큰 쪽을 고른다.
  • 메모리 줄이기: dp[i]는 dp[i − 1], dp[i − 2]만 읽으니 변수 두 개로 충분하다. 집이 100만 개라도 리스트를 새로 만들 필요가 없다.
4단계 · 코드 흐름
  1. best_line(a): prev2 = prev1 = 0에서 시작해, 집마다 (prev2, prev1) = (prev1, max(prev1, prev2 + 돈)).
  2. max(best_line(첫 집 ~ 마지막 앞 집), best_line(둘째 집 ~ 마지막 집))을 돌려준다.
5단계 · 파이썬 코드 
def best_line(a):
    prev2, prev1 = 0, 0                       # dp[i-2], dp[i-1]
    for x in a:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

def solution(money):
    # 첫 집과 마지막 집은 이웃이라 둘 중 하나는 안 턴다
    return max(best_line(money[:-1]), best_line(money[1:]))
  • prev2, prev1 = prev1, max(...): 오른쪽을 다 계산한 뒤 한꺼번에 넣는다. 한 줄씩 나눠 쓰면 prev1이 먼저 바뀌어 틀린다.
  • money[:-1], money[1:]: 마지막 집을 뺀 것, 첫 집을 뺀 것이다. 슬라이스는 복사본을 만든다. 100만 개면 잠깐 두 배 메모리를 쓰지만 문제없다.
6단계 · 실행 추적

[2, 7, 9, 3, 1]을 한 줄로 보면

집 2 7 9 3 1
dp 2 max(2, 0 + 7) = 7 max(7, 2 + 9) = 11 max(11, 7 + 3) = 11 max(11, 11 + 1) = 12

한 줄이면 12(2 + 9 + 1)다. 동그라미에서는 첫 집 2와 마지막 집 1이 이웃이라 안 된다. 마지막 집을 뺀 [2, 7, 9, 3]은 11, 첫 집을 뺀 [7, 9, 3, 1]은 10이라 답은 11이다.

7단계 · 복잡도와 흔한 실수

\(O(n)\) 시간, 변수 몇 개의 공간이다. 집 100만 개로 재 보니 0.1초가 안 걸렸다.

  • 동그라미를 잊고 한 줄로 한 번만 풀어 첫 집과 마지막 집을 함께 턴다.
  • “첫 집을 턴다/안 턴다”로 나누면서, 턴 경우에 마지막 집을 빼지 않는다.
  • 짝수 번째 합과 홀수 번째 합 중 큰 쪽을 고른다. [5, 1, 1, 5, 1, 1]은 둘 다 7이지만, 사이를 두 칸 띄워 첫째와 넷째를 털면 10이다.
검증: 문제의 예시와 6단계의 표, 두 한 줄의 값을 코드로 확인했다. 무작위 입력 3,000개(집 12개 이하)에서 “털 집을 모두 골라 동그랗게 이웃하지 않는지 보는” 풀이와 결과가 같았다. 집 100만 개의 시간도 쟀다 — 30_pg42897_p1.py

  1. 프로그래머스 스쿨, “도둑질” (https://school.programmers.co.kr/learn/courses/30/lessons/42897), 2026-09-30 조회. ↩