도둑질

문제 설명

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

 

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

 

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

 

제한사항

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

---

문제 해설

 

DP문제의 기본이다. 스티커 때기 문제유형으로 주변의 객체를 참조하지 못하게 하는 것 이 중점이다.

 

전방위탐색을 돌리게 되면, 집의 객체수가 매우 많기 때문에 무조건 시간초과 한다.

 

그럼으로 값을 누적시켜가면서, 진행해야 한다.

---

첫 번째 시도

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

using namespace std;

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

    vector<int> DP2(money.size(), 0);
    DP2[0] = 0;
    DP2[1] = money[1];
    for (int i = 2; i < money.size(); i++)
        DP2[i] = max(DP2[i - 1], DP2[i - 2] + money[i]);
    return max(*max_element(DP1.begin(), DP1.end()), *max_element(DP2.begin(), DP2.end()));
}

성공

 

객체들이 원형으로 이어져 있다는 사실은 처음에만 중요하다. 첫 집을 선택할때, 1번을 선택하고 진행할지 2번을 선택하고 진행할지 만 고민하면 된다.

 

전체 객체의 수 만큼 DP배열을 생성하고 진행한다. DP1은 첫번째 집을 선택한다고 가정하고 진행한다.

 

DP[0]은 1번째 집을 선택하고 그 이후 배열을 참조한다는 의미이다. 첫번쨰 집을 선택하였을 때는 집들이 이어져있기 때문에, 맨 마지막 배열을 참조하지 않아도 된다.

 

DP[1]은 DP[0]과 DP[1]을 비교하였을 때, 0번째와 1번째의 객체의 값을 비교하여 첫번째를 털지 두번째를털지 비교하기 위해 집어넣는다.

 

for문으로 전채순환을 하되, 시작점은 2번째, (0번째와 1번째는 이미 값을 기입하였음으로) 끝은 Size의 -1번째까지 진행한다.

 

이제부터 이전값과 비교하면서 진행한다. DP1의 i번째 값은 바로 전 값과 전전값 + 현재값 을 비교하여 집을 털지 말지를 고민한다.

 

여기서 바로 전 값은, 바로전에 집을 털었을 경우 재산을 의미하고, 전전값은 저번에 집을 털지 않았을 때의 재산을 의미한다.

 

즉, 현재 집을 털지 여부 =  저번집을 털었을때 돈이 더 많은가? 아니면 저번집을 털지 않고, 현재집을 털었을 때 돈이 더 많은가 가 된다.

 

초기 시작값이 1번일 때, 2번일 때를 비교해서, 첫번째 집을 털었을 때와 털지 않았을 때를 기준으로 순환참조를 한 뒤, DP1과 DP2의 최대값 중 더 큰 값이 최적의 값이 된다.