Programers 도둑질

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

코딩테스트 연습 - 도둑질

프로그래머스 도둑질 문제입니다.

 

#include <string>
#include <vector>

using namespace std;
int max(int a,int b){
    return a>b?a:b;
}
int solution(vector<int> money) {
    vector<int> dp1(money.size(),0);
    vector<int> dp2(money.size(),0);
    dp1[0] = money[0];
    dp1[1] = money[0];
    dp2[1] = money[1];
    
    //첫번째 -> 마지막전
    for(int i = 2; i<dp1.size()-1;i++){
        dp1[i] = max(dp1[i-1], dp1[i-2] + money[i]);
    }
    //두번째 -> 마지막
    for(int i = 2; i<dp1.size();i++){
        dp2[i] = max(dp2[i-1], dp2[i-2] + money[i]);
    }
    
    int answer = max(dp1[dp1.size()-2], dp2[dp2.size()-1]);
    return answer;
}

아이디어

이 문제를 처음 풀이 했을때는 동그랗게 배치되어 있다는 것을 간과하고 단순하게 점화식을 세워서 호되게 혼났다

동그란 배치때문에 첫번째 집과 마지막 집이 인접한 집으로 처리를 할 방법을 고민해야 했음

한번의 점화식으로 해결하는 방법을 찾지 못하고 첫번째를 털때는 마지막집을 방문하지않고, 두번째집을 털때는 마지막집까지 방문하는 두개의 경우의 수로 나누어서 처리 했음