[프로그래머스/c++] 도둑질

문제

원형으로 이루어진 마을의 집에는 돈이 있다. 인접한 두 집을 털면 경보가 울린다.
이 때, 도둑이 훔칠 수 있는 돈의 최댓값을 구한다.

---

접근

• 규칙을 한번에 찾기 힘든 문제라 배열의 길이를 늘리면서 생각해보았다.
• [1, 2]
  • 집이 2개라면 당연히 돈이 더 많은 2를 선택
• [1, 2, 3]
  • 집이 3개라면 당연히 3 선택
• [1, 2, 3, 4]
  • 2와 4 선택
• [1, 10, 20, 4, 40]
  • 20과 40 선택
• 그렇다면 점화식은 어떻게 세워야 할까???
• [1, 10, 20, 4, 40]을 자세히 살펴보면
• 최대한 큰 수를 고를 수 있는 모든 경우를 알아보기 위해, 각 위치에서 최대한 큰 값을 고를 수 있는 경우를 알아야 한다.
• 앞에서부터 각 위치에서 가장 큰 경우를 따져보자.
  • 1: 가장 큰 경우는 당연히 자기 자신인 1을 선택하는 경우
  • 10: 10을 선택
  • 20: 2번째 값을 고르면 자기 자신을 선택하지 못한다. 그렇다면 1과 20을 고르는 경우와 10을 고르는 경우로 나뉜다. 당연히 21이 크므로 이를 선택한다.
  • 현재까지 [1, 10, 21, 4, 40]
  • 4: 4를 선택하면 10의 위치에서 고를 수 있는 최고값을 자기자신의 값에 더할 수 있다. 바로 앞의 21을 고르면 자기 자신을 선택할 수 없다. 둘 중 21이 더 크므로 이를 선택한다.
  • 현재까지 [1, 10, 21, 21, 40]
  • 일반화하면 dp[now]=max(dp[now-1], dp[now-2]+dp[now])
  • 40: 똑같이 적용하면 max(21, 21+40)인데 21+40에서 21은 첫 번째 값을 포함하고 40은 마지막 값을 나타낸다. 이 때 첫 번째와 마지막은 연결되어 있으므로 둘을 동시에 선택할 수는 없다.
    • 따라서 이 문제를 해결하기 위해 배열을 두 개로 나누어야 한다.
    • 첫번째를 선택하면 마지막을 선택하지 못하고, 마지막을 선택하면 첫번째를 선택하지 못하므로
    • [1, 10, 20, 4]와 [10, 20, 4, 40]으로 분리하여 DP 점화식을 적용시켜야 한다.
    • 하지만 이 dp 점화식의 경우 3번째 위치부터 적용가능하므로 1번째와 2번째 위치를 비교하지 못한다.
    • 두 배열의 각각 앞에 0을 추가하여 모든 경우를 고려할 수 있도록 한다.
    • [0, 1, 10, 2, 4]와 [0, 10, 20, 4, 40] 이 두 배열에 대해 점화식을 적용하고 마지막 원소의 최댓값을 비교하여 더 큰 값이 도둑이 훔칠 수 있는 돈의 최댓값이 된다.

 

 

---

성공 코드(내 코드)

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> money) {
    int answer = 0;
    vector<int> dp1, dp2;
    dp1.push_back(0);
    dp2.push_back(0);
    for(int i=0; i<money.size()-1; i++){
        dp1.push_back(money[i]);
        dp2.push_back(money[i+1]);
    }
    for(int i=2; i<dp1.size(); i++){
        if(dp1[i-1]>dp1[i-2]+dp1[i]){
            dp1[i]=dp1[i-1];
        } else{
            dp1[i]=dp1[i-2]+dp1[i];
        }
        if(dp2[i-1]>dp2[i-2]+dp2[i]){
            dp2[i]=dp2[i-1];
        } else{
            dp2[i]=dp2[i-2]+dp2[i];
        }
    }
    if(dp1[dp1.size()-1]>dp2[dp2.size()-1]){
        answer=dp1[dp1.size()-1];
    } else{
        answer=dp2[dp2.size()-1];
    }
    
    return answer;
}

---

후기

역시 level4 답게 고려할 사항들이 많았다. 배열을 두개로 분리하고 0을 앞에 추가하여 점화식을 적용해야 한다는 점을 생각해내는 것이 문제의 포인트인 것 같다!

 

---

참고

https://school.programmers.co.kr/questions/31576

프로그래머스