[프로그래머스] DP(6) 도둑질

문제 설명

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

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

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

 

제한 사항

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

 

풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> money) {
	
    // vector 동적 할당
    vector<int> dp1(money.size()); 
    vector<int> dp2(money.size() - 1);
    
    // 첫 번째 집부터 훔칠 경우
    dp1[0] = money[0];
    dp1[1] = money[0];
    
    // 두 번째 집부터 훔칠 경우
    dp2[0] = 0;
    dp2[1] = money[1];
    
    // dp1 max 값 비교
    for (int i = 2; i < money.size() - 1; i++) {
        dp1[i] = max(dp1[i-2] + money[i], dp1[i-1]);
    }
    
    // dp2 max 값 비교
    for (int i = 2; i < money.size(); i++) {
        dp2[i] = max(dp2[i-2] + money[i], dp2[i-1]);
    }
    
    // 최종 훔친 돈(dp1, dp2) 비교
    return max(dp1[money.size()-2], dp2[money.size()-1]);
}

 

풀이 설명

첫 번째 집부터 훔칠 경우(dp1), 두 번째 집부터 훔칠 경우(dp2) 총 2가지로 나눠 계산하고 최종적으로 훔친 돈을 비교한다.

 

연속한 집의 돈을 훔칠 수 없으므로,

dp1의 경우 dp1[0]은 money[0]이고, dp1[1]도 money[0]이 되고

dp2의 경우 dp2[0]은 0이고, dp2[1]은 money[1]로 초기화 한다.

 

두 집을 간격으로 n-2, n, n+2 .... 규칙으로 훔칠 수 있지만

n-2 + n < n-1 일 경우, 세 집을 간격으로 훔치게 된다.

 

따라서, 다음과 같이 값을 비교해 dp[i]에 max값을 넣는다.

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

 

dp1은 첫 번째 집부터 훔쳤으므로, 마지막 집을 훔칠 수 없다.(이웃하기 때문)

 

따라서, dp1과 dp2의 마지막 인덱스 값을 비교해 max 값을 뽑아낸다. 

max(dp1[money.size()-2], dp2[money.size()-1]);

 

해당 문제 링크

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

코딩테스트 연습 - 도둑질 | 프로그래머스