문제 설명

마을의 집들이 원형으로 배치되어 있다.

인접한 두 집을 동시에 털면 경보가 울리기 때문에,
서로 인접하지 않은 집들만 선택해서 털어야 한다.

훔칠 수 있는 돈의 최댓값을 구하는 문제이다.

---

핵심 포인트

이 문제는 대표적인 DP(동적 계획법) 문제인
"House Robber" 유형이다.

하지만 일반적인 문제와 다른 점은 집이 원형이라는 것이다.

즉,

• 첫 번째 집과 마지막 집도 서로 인접하다.

따라서 둘을 동시에 선택할 수 없다.

---

해결 아이디어

원형 구조 때문에 경우를 2개로 나눈다.

1. 첫 번째 집을 터는 경우

• 마지막 집은 선택 불가능
• money[:-1]

2. 첫 번째 집을 털지 않는 경우

• 마지막 집 선택 가능
• money[1:]

이 두 경우의 최댓값을 비교하면 된다.

---

점화식

현재 집을 털지 않는 경우와
현재 집을 터는 경우 중 더 큰 값을 선택한다.

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

의미:

• dp[i-1]

  • 현재 집을 털지 않음

• dp[i-2] + money[i]

  • 현재 집을 털음

---

코드

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

    # 일자 형태의 집에서 최댓값 계산
    def rob(arr):
        prev2 = 0
        prev1 = 0

        for m in arr:
            cur = max(prev1, prev2 + m)

            prev2 = prev1
            prev1 = cur

        return prev1

    # 첫 번째 집 포함, 마지막 집 제외
    case1 = rob(money[:-1])

    # 첫 번째 집 제외, 마지막 집 포함 가능
    case2 = rob(money[1:])

    return max(case1, case2)

---

동작 과정 예시

money = [1, 2, 3, 1]

case1

[1, 2, 3]

최댓값:

1 + 3 = 4

case2

[2, 3, 1]

최댓값:

3

따라서 정답은:

4

---

시간 복잡도

집을 한 번씩만 순회한다.

O(N)

• N ≤ 1,000,000 이므로
• 완전 탐색은 불가능
• DP 사용이 핵심이다.

---

느낀 점

처음에는 일반적인 DP 문제처럼 풀려고 했지만,
원형 구조 때문에 첫 번째 집과 마지막 집이 연결된다는 점을 고려해야 했다.

결국 문제를 두 개의 선형 DP 문제로 나누는 것이 핵심이었다.