[ 프로그래머스 도둑질 (Lv4) ] (C++)

프로그래머스의 도둑질(Lv4) 문제이다.

[ 문제풀이 ]

인접한 두 집을 털게 되면 경보가 울리게 된다. 즉, 현재 집을 턴다면, 현재 집 - 1, 현재 집 + 1의 집은 털지 못한다. 이 때, 훔칠 수 있는 최대 돈을 구해야 하는 문제이다.

우리가 구현해야 하는 solution 함수의 매개변수로는 vector가 호출되지만, 이 문제에서 그림을 보게 되면 집들은 서로 원형 모형을 하고 있다. 즉 ! vector의 0번째 Index와 가장 마지막 Index는 서로 인접한 상태라는 것을 알고 있어야 한다.

인접한 상태이기 때문에, 첫 번째 집(0번 Index)를 털게 된다면 가장 마지막 집은 털 수 없다는 것을 의미한다.

따라서, 본인은 2가지 경우로 나눠서 접근하였다.

1. 첫 번째 집(0번 Index)를 터는 경우.

2. 첫 번째 집(0번 Index)를 털지 않는 경우.

본인이 사용한 핵심변수는 DP[] 라는 int형 1차원 배열을 사용해 주었는데, DP[a] = b 의 의미는, "a번 집 까지 털었을 때, 훔칠 수 있는 돈의 최대 액수는 b원입니다" 라는 것을 의미한다. 그럼 지금부터 본격적으로 돈을 최대한 많이 털어보자.

우리가 'x'번 집을 털 때, 가장 많은 돈을 훔칠 수 있는 경우를 생각해보자.

우리에게는 2가지 선택지가 있다. "현재 x번 집을 터는 경우", "현재 x번 집을 털지 않는 경우". 이렇게 2가지의 선택지 중에서 더 큰 값을 찾아 나가면 되는 것이다.

"현재 x번 집을 터는 경우"는 그 값이 어떻게 될까??

x번 집을 털겠다 라는 것은, x - 1번 집과, x + 1번 집은 털지 못한다는 것을 의미한다.

즉 ! x - 2 번을 털었을 때의 최대액수 + x번 집을 털었을 때 훔칠 수 있는 액수가 "x번 집을 터는 경우의 구할 수 있는 최대액수"가 된다. 위에서 소개한 변수로 표현해본다면 DP[x] = DP[x - 2] + money[x] 가 된다.

반대로 털지 않는다면 어떻게 될까 ??

x번 집을 털지 않는다는 것은 x - 1번 집을 털 수 있다 라는 이야기이고, x번 집을 털지 않을 때 훔칠 수 있는 최대 액수는, "x - 1번집 까지 털었을 때의 최대액수"가 된다.

위에서 소개한 변수로 표현해 본다면 DP[x] = DP[x - 1]이 된다는 것이다.

우리는 위에서 말한 2가지 경우(터는 경우, 털지 않는 경우) 를 비교해가면서 최대값을 구해보면 된다.

수식으로 나타내보면 DP[x] = max(DP[x - 2] + money[x] , DP[x - 1]) 이 되는 것이다.

그런데 이 경우를 크게 2가지로 나눴다고 했다. 첫 번째 집을 터는 경우와 털지 않는 경우로 !

첫 번째 집을 터는 경우에는 DP[0] = money[0]이 될 것이다. 왜냐하면, 0번째 집까지 털었을 때, 획득할 수 있는 최대 액수는 0번째 집이 가지고 있는 그 액수일 것이기 때문이다. DP[1] = DP[0]이 될 것이다. 왜냐하면, 0번째 집을 털어버렸기 때문에, 1번째 집은 털 수 없다는 것을 의미하고, 1번째 집까지 털었을 때, 획득할 수 있는 최대 액수는 0번째 집을 털었을 때 획득한 액수 그대로 이기 때문이다.

반대로, 첫 번째 집을 털지 않는 경우는 어떻게 될까 ? DP[0] = 0 이 될 것이다. 0번 째 집을 털지 않으므로 "0번째 집 까지 털었을 때, 획득할 수 있는 최대액수는 0원" 이기 때문이다. 반대로, DP[1] = money[1]이 될 것이다.

본인은 실제 구현에서는 위의 상황을 구현하기 위해 2개의 DP 배열을 사용해주었다. DP[] 와 DP2[] 이다.

그래서 각각의 값을 구한 후, 최종적으로 n번째 집 까지 털었을 때의 최댓값과, n - 1번째 집 까지 털었을 때의 최대값을 비교해서 더 큰 값을 return 시켜주면 된다.

n - 1번째 집까지 털었을 때의 최대값을 비교하는 이유는, 첫 번째 집을 털게 되면 n 번째 집을 털지 못하게 되므로, 이 경우, n 번째 집까지 털었을 때 구할 수 있는 최대 액수는 n - 1번째 집까지 털었을 때의 구할 수 있는 최대 액수와 동일하기 때문이다.

[ 소스코드 ]

#include <string>
#include <vector>
 
#define MAX 1000010
using namespace std;
 
int DP[MAX];
int DP2[MAX];
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
int solution(vector<int> money)
{
    int n = money.size() - 1;
    DP[0] = money[0];
    DP[1] = DP[0];
    DP2[0] = 0;
    DP2[1] = money[1];
    
    for (int i = 2; i < n; i++)
    {
        DP[i] = Bigger(DP[i - 2] + money[i], DP[i - 1]);
    }
    for (int i = 2; i <= n; i++)
    {
        DP2[i] = Bigger(DP2[i - 2] + money[i], DP2[i - 1]);
    }
    
    return Bigger(DP[n - 1], DP2[n]);
}