[Programmers] #42897 - 도둑질 [Java][C++][Python]

문제 링크

---

1. 아이디어

집이 원형으로 배치되어 있어 인접한 두 집을 동시에 털 수 없다는 제약이 첫 집과 마지막 집도 서로 인접하다는 조건을 만든다. i번째 집을 털지 말지의 최적 선택은 그 이전 두 칸(dp[i-1], dp[i-2])까지 이미 얻어둔 최적 금액에만 의존하고, 그 금액을 얻기까지 구체적으로 어떤 집들을 골랐는지는 상관없다. 즉 작은 구간의 최적해가 더 큰 구간의 최적해를 구하는 데 그대로 재사용되므로, 앞에서부터 순서대로 최적해를 쌓아나가는 DP로 접근할 수 있다. 집이 일렬로 배치돼 있다면 dp[i]를 “i번째 집까지 봤을 때 훔칠 수 있는 최댓값”으로 두면, i번째 집을 안 털 때는 dp[i-1]을 그대로 가져오고 i번째 집을 털 때는 바로 옆집은 못 터니 dp[i-2]에 money[i - 1](money는 0-indexed이므로 i번째 집의 금액)을 더해, 두 값 중 큰 쪽을 택하는 dp[i] = max(dp[i-1], dp[i-2] + money[i - 1])가 성립한다. 원형에서는 여기에 첫 집과 마지막 집을 동시에 포함하는 경우만 추가로 배제하면 된다. 전체 구간을 “마지막 집을 제외한 구간”과 “첫 집을 제외한 구간” 두 개의 선형 구간으로 나누면, 각 구간에 위와 같은 방식의 DP를 그대로 적용한 뒤 두 결과 중 더 큰 값을 답으로 삼을 수 있다. 두 경우 모두 원형의 양 끝 집 중 하나는 항상 배제되므로 인접 제약을 만족하며, 각 구간을 계산할 때 아직 채워지지 않은 이전 두 칸은 0으로 취급해도 결과에 영향이 없어 별도의 경계 처리가 필요 없다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = money의 길이)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(int[] money) {
        int n = money.length;

        int case1 = func(money, 1, n - 1);
        int case2 = func(money, 2, n);
        return Math.max(case1, case2);
    }

    static int func(int[] money, int start, int end) {
        int n = money.length;
        int[] dp = new int[1 + n];

        for (int i = start; i <= end; i++) {
            dp[i] = Math.max(dp[i - 1], dp[(i - 2 + n) % n] + money[i - 1]);
        }

        return dp[end];
    }
}

#include <bits/stdc++.h>
using namespace std;

int func(vector<int>& money, int start, int end) {
    int n = money.size();
    vector<int> dp(1 + n);

    for (int i = start; i <= end; i++) {
        dp[i] = max(dp[i - 1], dp[(i - 2 + n) % n] + money[i - 1]);
    }

    return dp[end];
}

int solution(vector<int> money) {
    int n = money.size();

    int case1 = func(money, 1, n - 1);
    int case2 = func(money, 2, n);
    return max(case1, case2);
}

def func(money, start, end):
    n = len(money)
    dp = [0] * (1 + n)

    for i in range(start, end + 1):
        dp[i] = max(dp[i - 1], dp[i - 2] + money[i - 1])

    return dp[end]


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

    case1 = func(money, 1, n - 1)
    case2 = func(money, 2, n)
    return max(case1, case2)

---