[c++ 프로그래머스] (Lv.4) 도둑질

• 도둑질

문제 설명

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

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

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

제한사항

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

입출력 예moneyreturn

[1, 2, 3, 1]

4

---

풀이과정

1. DP를 이용하여 문제를 해결했습니다.

2. 문제에 집이 동그랗게 이어져 있고 집을 한 곳을 털 때 경보가 울린다는 것을 주의했습니다.

그래서 DP를 계산할 때 처음 집을 털 경우와 마지막 집을 털 경우 두 가지로 생각하여 해결했습니다.

(집이 원형으로 있기 때문에 첫 번째 집을 선택할 경우 마지막 집을 빼고 계산하는 식으로 했습니다)

start_dp[i - 1] = max(start_dp[i - 1] , start_dp[i - 2]);
start_dp[i] = max(start_dp[i - 1] , start_dp[i - 2] + money[i]);

집	2	1	2	3	1
첫집을 털은 수	2	2	4	5	-
마지막을 털은 수	-	1	2	4	4

3. DP를 돌면서 얻은 값들 중 최댓값을 반환합니다.

---

코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> money) {
    int answer = 0;
    vector<int> start_dp(money.begin() , money.end() - 1) , 
    end_dp(money.begin() + 1 , money.end());
    for(int i = 2 ; i < start_dp.size(); i++)
    {
        start_dp[i - 1] = max(start_dp[i - 1] , start_dp[i - 2]);
        start_dp[i] = max(start_dp[i - 1] , start_dp[i - 2] + money[i]);
    }
    for(auto a : start_dp) answer = max(answer,a);
    for(int i = 2 ; i < end_dp.size(); i++)
    {
        end_dp[i - 1] = max(end_dp[i - 1] , end_dp[i - 2]);
        end_dp[i] = max(end_dp[i - 1] , end_dp[i - 2] + money[i + 1]);
    }
    for(auto a : end_dp) answer = max(answer,a);
    return answer;
}