[Leetcode] 198. House Robber

Identifying the Problem

강도가 집을 털 때 가장 많이 훔칠 수 있는 경우를 구한다.

단, 바로 옆집으로 갈 경우 들키므로 바로 한 집과 바로 옆집을 털지 못한다. 

Organizing thoughts

홀수칸 털었을 때랑 짝수칸 털었을 때 비교해서

최대값 구하면 되는 거아닐까? 라는 생각을 했다.

이 경우 [2,1,1,2]를 설명할 수 없다.

 

생각해본 결과 단순한 규칙을 찾을 수 있었는데,

처음 집의 최대(problem)를 구하려면 다음 집, 그 다음 집의 최대(sub-problem)를 알아야 구할 수 있다.

 

Dynamic Programing으로 접근 가능하다.

 

끝 index부터 처음 index까지 최대값을 구하고 최종적으로

처음 index의 최대값을 리턴하면 된다. 

 

 

sum = 해당 인덱스에서 가능한 최대 값이다.

 

nums = [8,2,3,20,10,8,5]  같은 경우 패턴을 구하면,

 

sum[6] = 5

sum[5] = 8 과 sum[6] 중 큰 값

여기까지는 패턴이 존재하지 않으므로, 초기값으로 설정하고,

 

sum[4]  = 10 + sum[6] 과 sum[5] 중 큰 값 

sum[3] = 20 + sum[5] 과 sum[4] 중 큰 값 

sum[2] = 3 + sum[4] 과 sum [3] 중 큰 값

sum[1] = 2 + sum[3] 과 sum[2] 중 큰 값

sum[0] = 8 + sum[2] 과 sum[1] 중 큰 값

 

이후로는 패턴이 나타나기 시작한다.

Sourcecode

int rob(int* nums, int numsSize)
{
	int* sum = malloc(sizeof(int) * numsSize);
	
	if(numsSize  == 0) return 0;
	else if(numsSize  == 1) return nums[0];
	else if (numsSize  == 2) return nums[0] > nums[1] ? nums[0] : nums[1]; 

	sum[numsSize - 1] = nums[numsSize - 1];
	sum[numsSize - 2] = nums[numsSize - 2] > nums[numsSize - 1] ? 	nums[numsSize - 2] : nums[numsSize - 1];

	
	for(int i = numsSize-3; i>=0;i--)
	{
		sum[i] = nums[i] + sum[i+2] > sum[i+1] ? nums[i] + sum[i+2] > sum[i+1];
	}

	return sum[0];
}