도둑질 - level 4

해결방법

이 문제는 처음에 0번을 터는 수와 1번을 터는 수로 나눌 수 있다. 인접한 집을 털 수 없기 때문에 이전전 집과 현재와 이전 집중에 누가 큰지가 현재 값이 된다.
$$ dp[0][i] = max(dp[0][i-1], dp[0][i-2] + money[i]) $$
$$ dp[1][i] = max(dp[0][i-1], do[0][i-2] + money[i]) $$
위의 점화식을 보면 똑같이 보이겠지만 위에 점화식은 처음 집을 털 경우이므로 마지막집은 항상 털면 안되고, 아래 점화식은 2번째 집부터 털기 때문에 마지막집을 털어도 된다. 점화식을 통해 dp는 2 * 집의 수만큼 2차원 배열로 정의했다.

 int dp[2][1000001];

아래는 초기화 코드이다. dp[0][1]에도 넣어준 이유는 반복문 인덱스를 2번부터 시작하기 때문에 0번과 1번을 둘다 초기화 시켜주어야 한다. dp[1][1]만 초기화 시킨이유는 dp[1][0]은 털지 않고 시작하기 때문이다.

dp[0][0] = money[0], dp[0][1] = max(money[0], money[1]);
dp[1][1] = money[1];

점화식을 그대로 옮겨서 money.size()까지 반복한다.

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

dp[0]에 있는 것은 항상 마지막 집을 털면 안되기 때문에 마지막 앞집까지의 최고점과 dp[1]의 마지막 집까지의 최고점 중 최고점이 정답이다.

answer = max(dp[0][money.size()-2], dp[1][money.size()-1]);

전체 소스코드

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int dp[2][10000001];
int solution(vector<int> money) {
    int answer = 0;
    dp[0][0] = money[0], dp[0][1] = max(money[0], money[1]);
    dp[1][1] = money[1];
    for(int i = 2; i < money.size(); ++i) {
        dp[0][i] = max(dp[0][i-1], dp[0][i-2] + money[i]);
        dp[1][i] = max(dp[1][i-1], dp[1][i-2] + money[i]);
    }
    return answer = max(dp[0][money.size()-2], dp[1][money.size()-1]);
}

[출처] https://programmers.co.kr/learn/courses/30/lessons/42897