프로그래머스[Lv.4] - 도둑질

 

 

문제 설명

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

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

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

https://school.programmers.co.kr/learn/courses/30/lessons/42897

---

 

 

 

 

 

 

제한 사항

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

---

 

 

 

 

 

 

풀이

문제를 요약하면, 원형으로 배치된 집에서 최대한 많은 돈을 가져가면 된다.

단, 연속된 집에서는 돈을 가져갈 수 없다.

 

해당 문제는 dp를 이용하면 쉽게 풀 수 있다.

하지만, 다른 문제에 비해 어려운 점은 집이 원형으로 배치되어 있다는 점이다.

집이 원형으로 배치되어 있어 첫 번째 집과 마지막 집이 연속하다고 할 수 있다.

 

감을 잡기 위해 집이 원형이 아닌 일렬로 배치되어 있다고 생각해 보자.

그렇다면 i번째 집은 i-2번째 집까지의 최댓값에 i번째 집의 돈을 더한것 과 i-1번째 집까지의 최댓값 중 하나를 선택할 수 있다.

이를 식으로 나타내면 다음과 같다.

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

 

이제, 원형을 어떻게 처리할지 고민해 보자.

일렬로 배치된 것과 원형으로 배치된 것의 유일한 차이는 첫 집과 마지막 집이 어떻게 연결되는가의 차이이다.

• 첫 집을 선택할 경우, 마지막 집은 선택할 수 없다.
• 첫 집을 선택하지 않은 경우, 마지막 집을 선택할 수 있다.

이 두가지 경우가 모든 경우이기 때문에 이 경우들을 모두 처리하면 답을 구할 수 있다.

//0번을 선택
dpFirst[1] = money[0];
for(int i = 2; i < N; i++)
{
    dpFirst[i] = max(dpFirst[i-1], dpFirst[i-2] + money[i-1]);
    answer = max(answer, dpFirst[i]);
}

//0번을 선택 X
for(int i = 2; i <= N; i++)
{
    dpSecond[i] = max(dpSecond[i-1], dpSecond[i-2] + money[i-1]);
    answer = max(answer, dpSecond[i]);
}

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> money) {
    int answer = 0;
    
    int N = money.size();
    vector<int> dpFirst(money.size()+1, 0);
    vector<int> dpSecond(money.size()+1, 0);
    
    //0번을 선택
    dpFirst[1] = money[0];
    for(int i = 2; i < N; i++)
    {
        dpFirst[i] = max(dpFirst[i-1], dpFirst[i-2] + money[i-1]);
        answer = max(answer, dpFirst[i]);
    }
    
    //0번을 선택 X
    for(int i = 2; i <= N; i++)
    {
        dpSecond[i] = max(dpSecond[i-1], dpSecond[i-2] + money[i-1]);
        answer = max(answer, dpSecond[i]);
    }
    
    return answer;
}

---