[프로그래머스] 도둑질

문제 설명

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

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

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

제한사항

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

---

풀이

80분
집이 원형으로 이어져있으므로 첫 집을 방문하는 경우와 그렇지 않은 경우로 나누는 것에는 빠르게 접근할 수 있었다. 하지만 처음에는 dfs방식에 동적계획법을 적용했었는데, 해당 코드로는 효율성 테스트를 통과할 수 없었다. 이때부터 긴 긴 시간을 고민하게 되었다. ‘옆집은 방문할 수 없으니, +2 혹은 +3한 인덱스가 다음 방문 지점’이라는 점에 꽂혀서, money배열을 한 번만 순회하는 방법은 생각하지 못했다. 결국 다른 사람의 풀이과정 중

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

의 힌트를 얻게 되어 풀 수 있었다.

코드

// 12:04 ~ 13:20
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

vector<int> cache;
vector<int> money;

void solve(){
    for(int i = 2; i < money.size(); ++i){
        cache[i] = max(cache[i-2] + money[i],cache[i-1]);
    }
}

int solution(vector<int> _money) {
    int res = -1;
    money = _money;
    
    cache.resize(money.size(),0);
    cache[0] = money[0];
    cache[1] = money[0];
    solve();
    res = cache[money.size()-2];
    
    cache.assign(money.size(),0);
    cache[0] = 0;
    cache[1] = money[1];
    solve();
    res = max(res,cache[money.size()-1]);
    
    return res;
}