프로그래머스

프로그래머스 도둑질 풀이: 원형 집을 두 구간으로 나누는 동적 계획법

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

0. 문제 링크와 출처

선형 배열이라면 익숙한 선택/건너뛰기 DP지만, 원형에서는 첫 집과 마지막 집의 동시 선택을 막아야 한다. 두 경우로 나눈 뒤 같은 점화식을 적용하면 되므로 Level 3으로 판단했다.

문제 원문과 제한 조건은 변경될 수 있으므로 제출 전에 공식 문제 페이지를 다시 확인한다.

1. 문제 요약

각 집에 든 돈이 money 배열로 주어진다. 집들은 원형으로 배치되어 있어 인접한 두 집을 같은 밤에 털 수 없다. 훔칠 수 있는 금액의 최댓값을 반환한다.

중요한 조건은 다음과 같다.

  • 집은 3채 이상 1,000,000채 이하이다.
  • 각 집의 금액은 0 이상 1,000 이하이다.
  • 첫 번째 집과 마지막 집도 서로 인접한다.

예제 [1, 2, 3, 1]에서는 첫 집과 세 번째 집을 선택해 1 + 3 = 4를 얻을 수 있다.

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

첫 집과 마지막 집을 동시에 선택할 수 없다

원형 배열에 선형 DP 점화식을 그대로 적용하면 첫 집과 마지막 집이 서로 인접한다는 조건을 놓친다. 그러나 유효한 선택에서는 첫 집과 마지막 집을 함께 고를 수 없으므로, 모든 가능한 선택은 다음 둘 중 적어도 하나에 포함된다.

  1. 마지막 집을 제외하고 인덱스 [0, n - 1)만 고려한다.
  2. 첫 집을 제외하고 인덱스 [1, n)만 고려한다.

각 범위 안에서는 원형 끝점이 잘려 더는 서로 인접하지 않는다. 따라서 일반적인 선형 집 도둑질 점화식을 각각 적용하고 둘 중 큰 값을 고르면 된다. 첫 집과 마지막 집을 모두 제외하는 선택은 두 경우에 겹쳐 들어가도 최댓값에 영향을 주지 않는다.

한 구간 안에서는 선택과 건너뛰기만 비교한다

현재 집을 털지 않으면 이전 집까지의 최댓값을 유지한다. 현재 집을 털면 바로 앞 집은 건너뛰고 두 집 전까지의 최댓값에 현재 금액을 더한다.

현재 최댓값 = max(이전 집까지의 최댓값,
                  두 집 전까지의 최댓값 + 현재 집 금액)

현재 선형 구간에서 j번째로 처리하는 집의 금액을 value[j], 그 집까지의 최댓값을 dp[j]라고 하자. 집을 건너뛰면 직전 상태를 유지하고, 집을 털면 바로 앞 집을 건너뛰어야 한다.

dp[j] = max(dp[j - 1], dp[j - 2] + value[j])

코드에서는 DP 표를 만들지 않고 prev2와 prev1만 둔다. 각각 처리 직전의 두 칸 전과 한 칸 전 최댓값이다. 현재 집을 털 때의 금액은 prev2 + money[i], 건너뛸 때는 prev1이므로 둘 중 큰 값으로 갱신한다. 두 변수의 시작값 0은 아직 구간에서 처리한 집이 없는 상태를 뜻한다.

공식 예제에서 두 구간 비교하기

money = [1, 2, 3, 1]에서 마지막 집을 뺀 범위와 첫 집을 뺀 범위를 각각 계산한다. 표의 건너뜀은 이전 최댓값이고 털기는 두 집 전 최댓값에 현재 금액을 더한 값이다.

구간 집 인덱스와 금액 건너뜀 털기 현재 최댓값
마지막 집 제외 [0, 3) 0번 집 1 0 1 1
1번 집 2 1 2 2
2번 집 3 2 4 4
첫 집 제외 [1, 4) 1번 집 2 0 2 2
2번 집 3 2 3 3
3번 집 1 3 3 3

두 구간의 결과는 각각 4, 3이므로 정답은 4다. 마지막 집을 제외한 경우에는 첫 집과 세 번째 집을 고를 수 있고, 첫 집을 제외한 경우에는 첫 집과 마지막 집의 충돌을 걱정하지 않아도 된다.

선형 DP를 원형 배열 전체에 적용할 때의 반례

원형 조건을 무시하고 [8, 1, 1, 8] 전체에 선형 점화식을 적용하면 0번 집과 3번 집을 선택해 16이라고 계산할 수 있다. 원에서는 이 두 집이 이웃이므로 함께 털 수 없다. 두 구간으로 나누면 첫 집과 세 번째 집을 선택하는 8 + 1 = 9 또는 두 번째 집과 마지막 집을 선택하는 1 + 8 = 9가 최선이다.

원형 제약을 반영하지 않고 한 번만 선형 DP를 수행하는 접근은 끝점의 충돌을 구분하지 못한다. 두 끝점 중 하나를 반드시 제외하는 두 경우로 나누면 이 충돌을 점화식에 억지로 섞지 않고 처리할 수 있다.

배열 DP와 두 변수 DP 비교

DP 배열을 만들면 각 위치의 값을 확인하기 쉽지만 O(n) 공간이 든다. 이 문제는 각 구간에서 직전 두 값만 필요하므로 두 변수만으로 같은 결과를 낼 수 있다. 또한 money[:-1]과 money[1:]처럼 부분 배열을 복사하지 않고 시작·끝 인덱스를 넘긴다. 집이 백만 채까지 주어지는 조건에서 이 두 선택이 불필요한 메모리 사용을 막는다.

시간·공간 복잡도

길이가 n인 배열에서 최대 n - 1개 집으로 이루어진 두 구간을 한 번씩 처리하므로 시간 복잡도는 O(n)이다. 두 구간은 차례로 계산하고 각 계산에서 변수 몇 개만 유지하므로 추가 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

rob_linear(start, end)는 반열린 구간 [start, end)에서 인접한 집을 함께 선택하지 않을 때의 최댓값을 구한다. 첫 호출은 마지막 집을 제외하고, 두 번째 호출은 첫 집을 제외한다.

def solution(money):
    n = len(money)

    def rob_linear(start, end):
        prev2 = 0
        prev1 = 0

        for i in range(start, end):
            current = max(prev1, prev2 + money[i])
            prev2, prev1 = prev1, current

        return prev1

    return max(
        rob_linear(0, n - 1),  # 마지막 집을 제외
        rob_linear(1, n),      # 첫 집을 제외
    )

문제 제한에서 n >= 3이므로 두 구간은 모두 비어 있지 않다. prev2 = prev1 = 0은 현재 구간에서 아직 집을 처리하지 않은 상태를 나타내며, 금액이 0인 집도 별도 분기 없이 처리한다.

복사해 실행할 테스트

공식 예제, 최소 크기의 원형 경계, 끝점 충돌 반례, 최대 입력을 확인한다. 작은 입력은 전수 탐색 기준값과 비교할 수 있도록 같은 테스트 블록에 검증 함수도 둔다.

from itertools import product


def brute_force(money):
    n = len(money)
    best = 0

    for mask in range(1 << n):
        has_adjacent_houses = any(
            (mask >> i) & 1 and (mask >> ((i + 1) % n)) & 1
            for i in range(n)
        )
        if has_adjacent_houses:
            continue

        total = sum(money[i] for i in range(n) if (mask >> i) & 1)
        best = max(best, total)

    return best


assert solution([1, 2, 3, 1]) == 4
assert solution([2, 3, 2]) == 3
assert solution([8, 1, 1, 8]) == 9
assert solution([0, 0, 0]) == 0
assert solution([1000] * 1_000_000) == 500_000_000

for size in range(3, 8):
    for values in product(range(3), repeat=size):
        assert solution(list(values)) == brute_force(values)

4. 공식 예제와 추가 검증

작성한 solution을 Python으로 실행했다. 명시한 사례 외에도 길이 37, 금액 02인 모든 배열을 만들어 가능한 집 선택을 전부 확인한 결과와 비교했다.

공식 예제

입력: money = [1, 2, 3, 1]
기대 출력: 4
실행 결과: 통과
검증 목적: 원형 배치에서 두 선형 구간의 최댓값 비교 확인

추가 검증 1: 최소 집 수에서 양 끝 집이 이웃인 경우

입력: money = [2, 3, 2]
기대 출력: 3
실행 결과: 통과
검증 목적: 첫 집과 마지막 집을 함께 고르지 않는지 확인

추가 검증 2: 선형 점화식만 적용하면 끝점을 함께 고르는 경우

입력: money = [8, 1, 1, 8]
기대 출력: 9
실행 결과: 통과
검증 목적: 원형에서 인접한 첫 집과 마지막 집의 동시 선택 방지 확인

추가 검증 3: 최대 입력 크기와 동일한 금액

입력: 집 1,000,000채, 각 집의 금액 = 1,000
기대 출력: 500,000,000
실행 결과: 통과
검증 목적: 원형에서 선택할 수 있는 집이 최대 500,000채이고, 최대 금액 합이 500,000,000임을 확인

추가 검증 4: 작은 입력 전수 비교

입력: 집 수 3~7, 각 집의 금액은 0, 1, 2 중 하나인 모든 배열
기대 결과: DP 결과가 모든 집 선택 조합을 직접 확인한 최댓값과 일치
실행 결과: 통과
검증 목적: 여러 금액 패턴에서 원형 인접 조건과 구간 경계 분할을 함께 확인

5. 다른 풀이 방식 검색 및 비교

NeetCode의 설명에는 첫 집 선택 여부를 상태로 둔 재귀·메모이제이션 풀이도 있다. 상태가 명시적이라 확장하기 쉽지만, 이 문제에서는 첫 집 포함 여부를 두 범위로 나누면 재귀 상태를 추가할 필요가 없다. 같은 선형 점화식을 두 번 적용하고 직전 두 값만 보관해 O(n) 시간, O(1) 추가 공간으로 마무리한다.

마무리

이 문제에서는 원형 제약을 점화식 안에서 직접 처리할 필요가 없다. 첫 집을 포함할 수 있는 구간과 첫 집을 제외하는 구간을 각각 선형 DP로 풀면 끝점 충돌이 사라진다. 구간 경계만 정확히 나눈 뒤 prev1과 prev2를 갱신하는 것이 핵심이다.

관련 문제

  • House Robber — 한 줄로 놓인 집에서 같은 선택/건너뛰기 점화식을 적용하는 Level 3 동적 계획법 문제.
#동적계획법#프로그래머스#난이도 3