도둑질

• 도둑질

문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력 예moneyreturn

[1, 2, 3, 1]

4

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int dp1[1000000];
int dp2[1000000];
int solution(vector<int> money) {
    int answer = 0;
    dp1[0]=money[0];
    dp1[1]=money[0];
    dp2[0]=0;
    dp2[1]=money[1];
    for(int i = 2; i < money.size(); i++){
        dp1[i]=max(dp1[i-2]+money[i],dp1[i-1]);
    }
    for(int i = 2; i <=money.size(); i++){
        dp2[i]=max(dp2[i-2]+money[i],dp2[i-1]);
    }
    cout << dp1[money.size()-1] <<dp2[money.size()-1];
    
    return max(dp1[money.size()-2],dp2[money.size()-1]);
}

 

추가적으로 여기까지는 첫번째집을 선택했을 경우다. 하지만 첫번째 집을 선택하지 않는 경우도 고려해줘야한다.

2번째집을 선택하는 경우 똑같이 해주면 된다 . 범위를 하나 더 뒤까지 고려해줘야한다.

이건 마을이 원형이라 생기는 고려사항인데 이해안되면 댓글 달아주세용~_~