DP문제인 걸 알고 봐서 어떻게든 생각을 했는데 뭔가 알듯말듯..했다.
처음 코드를 짤 때, dp[i-1]의 값과 비교하지 않아서 틀렸었다. 그래서...쪼금 도움을 받아서 풀었다.
문제 링크:
https://school.programmers.co.kr/learn/courses/30/lessons/42897
이 문제에서 고려할 점은
- i와 그 양쪽인 i-1, i+1의 집 중 하나를 털 경우 경보가 울린다.
- 첫 번째와 마지막 집도 이웃이다.
dp배열을 하나 만들고 첫 집부터 마지막 집까지 털때마다 최대로 가져올 수 있는 값을 dp배열에다가 저장해준다. 그래서 점화식으로 나타내보면 아래와 같다.
dp[i] = max(dp[i-2] + money[i], dp[i-1])
그런데 여기서 첫 번째 집과 마지막 집이 이웃으로 연결되어 있으므로 두 가지 경우로 나누어서 구한다음 그 중 더 큰 값을 리턴해주면 된다.
- 첫 번째 집을 털고 마지막 집을 안 터는 경우
- 첫 번째 집을 안 털고 마지막 집을 터는 경우
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> money){
int n = money.size();
vector<int> dp1(n,0);
vector<int> dp2(n,0);
//첫 번째 집을 털고 마지막 집을 안 터는 경우
dp1[0] = money[0];
dp1[1] = max(money[0],money[1]);
for(int i=2;i<n-1;i++){
dp1[i] = max(money[i] + dp1[i-2],dp1[i-1]);
}
//마지막 집은 털고 첫 번째 집을 안 터는 경우
dp2[1] = money[1];
for(int i=2;i<money.size();i++){
dp2[i] = max(money[i] + dp2[i-2],dp2[i-1]);
}
//두 값 중 최댓값
int answer = max(dp1[n-2],dp2[n-1]);
return answer;
}
int main(void){
vector<int> money = {1,2,3,1};
int result = solution(money);
cout<<result<<'\n';
}
