이 문제에서는 각기 서로 다른 가치를 지닌 n개의 집이 주어지며, 우리의 과제는 도둑이 훔칠 수 있는 최대 가치를 구하는 것입니다.
문제 설명
각 집에 보관된 가치를 담고 있는 배열 houses[]가 주어집니다. 도둑은 이 집들을 털지만, 이웃들이 절도 사실을 알아차릴 수 있기 때문에 인접한 두 집을 연달아 털 수는 없습니다. 즉, 들키지 않고 훔칠 수 있는 금액의 최대 합을 구해야 합니다.
예시를 통해 문제를 살펴보겠습니다.
입력
houses[] = {5, 2, 1, 6, 7, 9, 4, 3}
출력
23
설명
최대 가치를 훔치는 조합은 : 5, 6, 9, 3 입니다.
해결 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용해 해결할 수 있습니다. 도둑이 인덱스 i에 위치한 집을 털었다면, 바로 옆에 있는 인덱스 (i+1)과 (i-1)의 집은 털 수 없습니다.
문제를 해결하기 위해 크기가 n인 DP 배열을 생성합니다. 기저 사례(base case)로 DP[0]에는 houses[0]을, DP[1]에는 houses[0]과 houses[1] 중 더 큰 값을 초기화합니다. 이후 인덱스 2부터 n-1까지 아래 점화식으로 DP 배열을 채워 나갑니다.
DP[i] = max(DP[i-2] + houses[i], DP[i-1])
즉, 현재 집을 털어서 얻는 값(DP[i-2] + houses[i])과 현재 집을 건너뛰는 경우(DP[i-1]) 중 더 큰 값을 선택하는 방식입니다. 최종적으로 DP 배열의 마지막 값이 훔칠 수 있는 최대 가치가 되며, 시간·공간 복잡도는 모두 O(n)입니다.
구현 예제
#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 배열 전체 대신 변수 두 개만 유지하면 되므로, 공간 복잡도를 O(n)에서 O(1)로 줄일 수 있습니다.
최적화된 구현 예제
#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
정리하면, 인접한 집을 동시에 털 수 없다는 제약 조건 속에서 동적 계획법의 점화식을 세우면 문제를 깔끔하게 해결할 수 있으며, 직전 두 값만 저장하는 방식으로 메모리 사용량까지 최적화할 수 있습니다.