프로그래머스 동적계획법 도둑질 c++ 풀이

문제 설명

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

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

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

제한사항

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

입출력 예

money	return
[1, 2, 3, 1]	4

 

 

문제 풀이

처음엔 집 갯수가 홀수개인 경우랑 짝수개인 경우로 나눠서 생각해보려고 하다가... 홀수일 경우에 경우의 수 구하기가 빡세서 그만 뒀다.

계속 삽질하다가 블로그에서  점화식을 세워보라는 힌트를 얻고 점화식을 세워 보았다.

일단 경우는 첫 집을 털 경우와 첫 집을 건너 뛸 경우로 나누고 각각의 집 i까지의 최대 금액을 dp[i]라고 하면
또 경우가 두개로 나뉘는데, 현재 집의 인덱스를 i라고 할 때 전전집인 i-2와 현재집을 턴 경우와 바로 이전 집인 i-1을 털었을 경우이다.
따라서 점화식은 다음과 같다. dp[i] = max(dp[i-2]+money[i], dp[i-1])

위 방법을 코드로 구현하면 다음과 같다.

int solution(vector<int> money)
{
    int answer = 0;
    vector<int> dp1, dp2;
    dp1.push_back(money[0]);
    dp1.push_back(money[0]);
    dp2.push_back(0);
    dp2.push_back(money[1]);

    for (int i = 2; i < money.size() - 1; i++)
        dp1.push_back(max(dp1[i - 2] + money[i], dp1[i - 1]));
    for (int i = 2; i < money.size(); i++)
        dp2.push_back(max(dp2[i - 2] + money[i], dp2[i - 1]));
    answer = max(dp1[money.size() - 2], dp2[money.size() - 1]);

    return answer;
}