[프로그래머스] 도둑질 c++

풀이

첫번째 집과 마지막 집에 옆에 있으므로 마지막 집을 털게되면 첫번째 집을 털지 못한다.

처음부터 첫번째 집을 터는 경우와 털지 않는 경우로 나누어서 구해야한다.
dp[i] 는 i까지 터는 경우의 최댓값이다. 
2번 전 집을 털고 i번째 집을 터는 경우와 털지 않고 i-1번째까지의 최댓값을 가져오는 경우가 있다.

#include <string>
#include <vector>
#include <algorithm>


using namespace std;
vector<int>dp1; 
vector<int>dp2; 
int solution(vector<int> money) {
    int answer = 0;
    dp1.resize(money.size());
    dp2.resize(money.size());
    int money_size = money.size();
    //첫번째 집을 터는 경우
    dp1[0] = money[0]; 
    dp1[1] = money[0];
    //첫번째 집을 털지 않는 경우
    dp2[0] = 0;       
    dp2[1] = money[1];
    
    for(int i=2;i<money_size;i++){
        if(i!=money_size-1)
            dp1[i] = max(dp1[i-2]+money[i] , dp1[i-1]);
        dp2[i] = max(dp2[i-2]+money[i] , dp2[i-1]);
    }
   
    return answer = max(dp1[money_size-2],dp2[money_size-1]);
}