문제 링크
1. 아이디어
동그랗게 배치된 집들에 대해 인접한 두 집을 연속으로 털 수 없을 때 도둑이 훔칠 수 있는 돈의 최댓값을 구해야 하는 문제다.
주어진 집들이 원형이 아니라 일렬로 이어져 있다고 하면, dp[i]를 첫 집부터 $i$번째 집까지만 고려했을 때 훔칠 수 있는 돈의 최댓값으로 정의할 수 있다. $i$번째 집 money[i - 1]을 털면 바로 이전 집은 털 수 없으므로 dp[i - 2] + money[i - 1], 안 털면 dp[i - 1]이다. 이 둘 중 큰 값을 취해 dp[i] = max(dp[i - 1], dp[i - 2] + money[i - 1])이 된다. 원형에서는 첫 집과 마지막 집이 서로 인접해 동시에 털 수 없으므로, 최적해는 둘 중 적어도 한 집을 반드시 제외한다. 따라서 마지막 집을 뺀 배열과 첫 집을 뺀 배열 각각에 이 점화식을 적용해 그중 큰 값을 답으로 삼으면, 두 경우가 가능한 모든 선택을 덮으므로 빠짐이 없다.
2. 복잡도
| 접근 | 시간 | 공간 |
|---|
| 배열 DP | $O(N)$ | $O(N)$ |
| 공간 최적화 DP | $O(N)$ | $O(1)$ |
($N$ = money의 길이)
3. 코드
풀이 1: 배열 DP [Java][C++][Python]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int solution(int[] money) {
int n = money.length;
int case1 = robRange(money, 1, n - 1);
int case2 = robRange(money, 2, n);
return Math.max(case1, case2);
}
static int robRange(int[] money, int l, int r) {
int n = money.length;
int[] dp = new int[1 + n];
for (int i = l; i <= r; i++) {
dp[i] = Math.max(dp[i - 1], dp[Math.max(i - 2, 0)] + money[i - 1]);
}
return dp[r];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <bits/stdc++.h>
using namespace std;
int rob_range(vector<int>& money, int l, int r) {
int n = money.size();
vector<int> dp(1 + n);
for (int i = l; i <= r; i++) {
dp[i] = max(dp[i - 1], dp[max(i - 2, 0)] + money[i - 1]);
}
return dp[r];
}
int solution(vector<int> money) {
int n = money.size();
int case1 = rob_range(money, 1, n - 1);
int case2 = rob_range(money, 2, n);
return max(case1, case2);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| def solution(money):
n = len(money)
def rob_range(l, r):
dp = [0] * (1 + n)
for i in range(l, r + 1):
dp[i] = max(dp[i - 1], dp[i - 2] + money[i - 1])
return dp[r]
case1 = rob_range(1, n - 1)
case2 = rob_range(2, n)
return max(case1, case2)
|
풀이 2: 공간 최적화 DP [Java][C++][Python]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int solution(int[] money) {
int n = money.length;
int case1 = robRange(money, 0, n - 1);
int case2 = robRange(money, 1, n);
return Math.max(case1, case2);
}
static int robRange(int[] money, int l, int r) {
int prv2 = 0, prv1 = 0;
for (int i = l; i < r; i++) {
int cur = Math.max(prv1, prv2 + money[i]);
prv2 = prv1;
prv1 = cur;
}
return prv1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
using namespace std;
int rob_range(vector<int>& money, int l, int r) {
int prv2 = 0, prv1 = 0;
for (int i = l; i < r; i++) {
int cur = max(prv1, prv2 + money[i]);
prv2 = prv1;
prv1 = cur;
}
return prv1;
}
int solution(vector<int> money) {
int n = money.size();
int case1 = rob_range(money, 0, n - 1);
int case2 = rob_range(money, 1, n);
return max(case1, case2);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| def solution(money):
n = len(money)
def rob_range(l, r):
prv2, prv1 = 0, 0
for i in range(l, r):
prv2, prv1 = prv1, max(prv1, prv2 + money[i])
return prv1
case1 = rob_range(0, n - 1)
case2 = rob_range(1, n)
return max(case1, case2)
|