인접하지 않는 최대 합 구하기

한 배열안에 있는 인접하지 않는 숫자들의 최대합을 구하는 문제를 풀어보겠습니다. 

 

여기서 인접하지 않는 가장 큰 최대합은 75, 120, 135입니다. 이를 구하기 위해서는 dp를 활용해야하는데 이전의 정보를 활용하면 편하게 진행할 수 있습니다.

 

array = [75, 105, 120, 75, 90, 135];

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

각 dp의 배열은 현재 위치의 최대 값을 의미한다. 

 

i는 현재의 위치를 의미하고 i-1은 이전의 최대값그리고 i-2는 한칸 띄어있는 위치의 최대 값이고 한칸 띄어져 있기 때문에  현재 위치의 배열 값을 더할 수 있다. 

 

이전의 값은 붙어 있기 때문에 현재의 값을 더할 수 없기 때문에 위의 점화식을 사용하면 인접하지 않는 수를 더한 가장 큰 값을 더할 수 있다. 

 

#include <vector>
using namespace std;

int maxSubsetSumNoAdjacent(vector<int> array) {
	if(array.size() == 0)
		return 0;
	
  vector<int> dp(array.size(), 0);
	
	dp[0] = array[0];
	dp[1] = max(array[0], array[1]);
	
	for(int i = 2; i < array.size(); i++){
		dp[i] = max(dp[i-1], dp[i-2] + array[i]);
	}
	
	return dp.back();
}