money = [1, 2, 3, 4, 5]
라고 가정하고 식 찾아보자.각 집을 털었을 때, 최댓값을 구해보자.
dp[0] = 1
dp[1] = 2 or 1
dp[2] = 1+3 or 2 or 1
dp[3] = 1+4 or 2+4 or 1+3 or 2 or 1
dp[4] = 2+5 or 3+5 or 1+4 or 2+4 or 1+3 or 2 or 1
규칙을 찾아보자.
dp[0] = 1 → money[0]
dp[1] = 2 or 1
→ max(money[0], money[1])
dp[2] = 1+3 or 2 or 1
→ max(dp[0]+money[2], dp[1])
dp[3] = 1+4 or 2+4 or 1+3 or 2 or 1
→ max(dp[1]+money[3], dp[2])
dp[4] = 2+5 or 3+5 or 1+4 or 2+4 or 1+3 or 2 or 1
→ 어 ? 규칙이 보이지 않는다.
➡️ 첫 번째 집과 마지막 집을 터는 경우를 나눠서 계산해야겠구나 ! 완전 독립적인 경우
모든 경우의 수 고려해서 코드를 짜보자.
마지막 집을 포함하여 집을 터는 경우
dp[0] = 0 → 0
dp[1] = 2 → money[1]
dp[2] = 3 or 2
→ max(dp[0]+money[2], dp[1])
dp[3] = 2+4 or 3 or 2
→ max(dp[1]+money[3], dp[2])
dp[4] = 2+5 or 3+5 or 2+4 or 3 or 2
→ max(dp[2]+money[4], dp[3])
✅ dp[i] = max(dp[i-2]+money[i], dp[i-1])
단, 최종 정답은 첫번째 집을 포함해 터는 경우, 마지막 집을 포함해 터는 경우의 최댓값으로 계산해줘야 한다.
#include <bits/stdc++.h>
#define MAX 1000001
using namespace std;
int dp1[MAX], dp2[MAX];
int answer;
int solution(vector<int> money) {
int houseNum = money.size();
// 첫번째 집 포함 털기
dp1[0] = money[0];
dp1[1] = max(money[0], money[1]);
for (int i = 2; i < houseNum-1; i++) {
dp1[i] = max(dp1[i-2] + money[i], dp1[i-1]);
}
// 마지막 집 포함 털기
dp2[1] = money[1];
for (int i = 2; i < houseNum; i++) {
dp2[i] = max(dp2[i-2] + money[i], dp2[i-1]);
}
answer = max(dp1[houseNum-2], dp2[houseNum-1]);
return answer;
}