이 문제에서는 몇 가지 값이 포함된 n개의 주택이 제공됩니다. 우리의 임무는 주택에서 가능한 최대 도난 가치를 찾는 것입니다.
문제 설명 − 각 하우스에 있는 값으로 구성된 배열 house[]가 있습니다. 도둑은 집을 훔치지만 이웃 사람들이 도둑질에 대해 알고 있는 것처럼 인접한 두 집에서 도둑질을 할 수 없습니다. 도둑이 집에서 잡히지 않고 훔칠 수 있는 최대한의 가치를 찾아야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
houses[] = {5, 2, 1, 6, 7, 9, 4, 3} 출력
23
설명
The max values can be stolen as : 5, 6, 9, 3.
솔루션 접근 방식
동적 프로그래밍을 사용하여 문제의 솔루션을 찾을 수 있습니다. 도둑이 지수 i에 있는 집에서 훔친다면 지수 (i+1)에 있는 집에서 훔칠 수 없도록 도둑이 훔친 최대 가치를 찾아야 하기 때문입니다. 또한 인덱스(i-1)에 있는 집에서 도둑질을 하지 않았을 것입니다. 문제를 해결하기 위해 크기가 n인 DP 배열을 만듭니다. 그리고 기본 사례의 경우 DP[0]을 주택[0]으로 초기화하고 DP[1]을 주택[1]로 초기화합니다. 그런 다음 인덱스 2에서 n-1까지 DP의 모든 값을 찾습니다. DP[i]의 값은 DP[i-2] + house[i] 또는 DP[i-1] 중 최대값이 됩니다. 그리고 결국 DP 배열의 마지막 값은 훔칠 수 있는 최대값입니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#include <iostream>
using namespace std;
int calMax(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxValuesStolen(int houses[], int n) {
if (n == 0)
return 0;
int DP[n];
DP[0] = houses[0];
DP[1] = calMax(houses[0], houses[1]);
for (int i = 2; i<n; i++)
DP[i] = calMax( (houses[i] + DP[i-2]), DP[i-1]);
return DP[n-1];
}
int main() {
int houses[] = {5, 2, 1, 6, 7, 9, 4, 3};
int n = sizeof(houses)/sizeof(houses[0]);
cout<<"The maximum possible values stolen from the houses is
"<<findMaxValuesStolen(houses, n);
return 0;
} 출력
The maximum possible values stolen from the houses is 23
이 솔루션은 좋지만 두 개의 값만 사용하여 도난당한 최대 값을 찾을 수 있다는 사실을 사용하여 더 효율적으로 만들 수 있습니다. DP에서와 같이 각 인덱스에 대해 두 개의 값만 사용했습니다. 따라서 문제에 대한 공간 복잡성을 줄이는 솔루션을 찾기 위해 두 개의 변수만 사용할 수 있습니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#include <iostream>
using namespace std;
int calMax(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxValuesStolen(int houses[], int n) {
if (n == 0)
return 0;
int maxValStolen;
int val1 = houses[0];
int val2 = calMax(houses[0], houses[1]);
for (int i = 2; i<n; i++) {
maxValStolen = calMax( (houses[i]+val1) , val2);
val1 = val2;
val2 = maxValStolen;
}
return maxValStolen;
}
int main() {
int houses[] = {5, 2, 1, 6, 7, 9, 4, 3};
int n = sizeof(houses)/sizeof(houses[0]);
cout<<"The maximum possible values stolen from the houses is "<<findMaxValuesStolen(houses, n);
return 0;
} 출력
The maximum possible values stolen from the houses is 23