(c++)프로그래머스 동적계획법 도둑질

문제 설명

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

 

 

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

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

 

제한사항

 

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

 

입출력 예

 

money	return
[1, 2, 3, 1]	4

 

---

나의 풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(vector<int> money) {
    int m1[1000001] = { 0 };
    int m2[1000001] = { 0 };
    m1[0] = money[0];
    m1[1] = money[0];
    m2[1] = money[1];
    for (int i = 2; i < money.size()-1; i++) {
        m1[i] = max(m1[i - 2] + money[i], m1[i - 1]);
    }
    for (int i = 2; i < money.size(); i++) {
        m2[i] = max(m2[i - 2] + money[i], m2[i - 1]);
    }
    return max(m1[money.size()-2],m2[money.size()-1]);
}

m1은 첫번째 집을 훔친 경우이고 m2는 첫번째 집을 훔치지 않은 경우의 수이다.

 

m1은 첫번째 집을 도둑질 했기 때문에 마지막집은 훔칠 수 없다. 때문에 money.size()-1까지만 반복한다.

 

i번째 집에서 벌 수 있는 가장 큰 수를 m1,m2[i]에 저장하는 것을 기본 알고리즘으로 사용하였다.