프로그래머스 도둑질

문제

https://programmers.co.kr/learn/courses/30/lessons/42897

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> money) {
    int answer = 0;
       
    vector<int> dp1(money.size(), 0);
    vector<int> dp2(money.size(), 0);
    
    dp1[0] = money[0];
    dp1[1]=money[0];
    for (int i = 2; i < money.size()-1; i++)
        dp1[i] = max(money[i] + dp1[i - 2], dp1[i - 1]);
   
    dp2[0] = 0;
    dp2[1] = money[1];
    for (int i = 2; i < money.size(); i++)
        dp2[i] = max(money[i] + dp2[i - 2], dp2[i - 1]);

    answer = max(dp1[money.size()-2],dp2[money.size()-1]);
    return answer;
}

풀이

원형으로 집이 배치된 마을이 있고 각각의 집에서 훔칠수 있는 돈을 입력으로 줍니다. 이웃된 두집을 털면 안될 때 최대로 훔칠 수 있는 돈을 리턴하는 문제입니다.

비슷한 dp문제들이 많이 있지만 마을 구조가 원형으로 되있는게 좀 까다로웠네요 저는 두개의 dp를 만들었습니다 첫번째 dp는 첫번째 집을 훔치고 시작합니다 이 경우에는 첫번째 집과 마지막집이 이웃되기 때문에 마지막 전집까지만 dp값을 구해줍니다. 두번째 dp는 첫번째 집을 건너 뛰고 시작해서 마지막집까지 dp값을 채워준뒤 둘중에서 큰값을 리턴해줬습니다.