[C++][프로그래머스] 도둑질

문제 설명은 더보기를 눌러주세요

문제 설명

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

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

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

제한사항

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

입출력 예

money                return

[1, 2, 3, 1]            4

 

 

-풀이-

1. 우선 하나 짚고 가야하는 것이 있습니다. 직관적으로 우리는 다음과 같은 상황에서 (* i / i+1 / i+2 / i+3 : 집)

i번째집을 털고, i+1, i+2, i+3 번째집을 털지 않는경우 i+2번째 집은 무조건 터는것이 좋다는 것을 알 수 있습니다.

그래서 고려할 것은 i번째 집을 털었을 경우 i+1, i+2번째 집에 대해서만 털지 안털지 고민해주면 됩니다.

 

2. 또 하나 고민할 것은, 집들이 동그랗게 되어있다는 것입니다. 그래서 두가지 경우로 생각해 볼 수 있습니다.

    1) 첫번째 집을 털었을 경우, (마지막-1)까지의 집까지만 고려해주면 됩니다. (마지막 집은 털 수 없으므로)

    2) 첫번째 집을 털지 않았을 경우, (마지막)까지만 고려해주면 됩니다. (마지막 집을 털 수도 있으므로)

    1)와 2)의 max값을 출력해주면 됩니다. 

 

-코드-

#include <string>
#include <vector>
#include <cstring>
using namespace std;
int getMaxMoney(int st, int en);
vector<int> Money;
int solution(vector<int> money) {
    int answer = 0;
    Money = money;
    answer = getMaxMoney(0, money.size()-1);
    answer = max(answer, getMaxMoney(1, money.size()));
    return answer;
}

// (money vector기준) st번째 집부터, en-1번째 집까지 털기
int getMaxMoney(int st, int en){ 
    int dp[1000000][3];
    memset(dp, 0, sizeof(dp)); // 초기화
    dp[st][0] = Money[st]; 
    
    for(int i=st+1; i<en; i++){
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + Money[i];
        dp[i][1] = dp[i-1][0];
        dp[i][2] = dp[i-1][1];
    }
    return max(dp[en-1][2], max(dp[en-1][0], dp[en-1][1]));
}