[LeetCode] 198. House Robber

 

강도가 집을 터는데 연속된 집을 털 수 없고 집마다 털 수 있는 금액이 nums[]로 주어질 때 가장 큰 값을 구하는 문제로 처음에는 재귀로 풀었는데 시간 초과가 떴다.

 

public void DFS(int i, int sum, int[] nums) {
	if (i >= nums.length) {
		answer = Math.max(answer, sum);
		return;
	}
    
    // 현재 집을 털 경우 sum에 더하고 연속된 집 건너뛰기 (i + 2)
    DFS(i + 2, sum + nums[i], nums);
    // 현재 집을 털지 않을 경우 sum에 더하지 않고 다음 집으로(i + 1)
    DFS(i + 1, sum, nums);
}

 

그래서 이전 집까지 털었을때의 최대값을 기록해두고 이를 이용하는 메모이제이션 방법으로 풀었다.

 

3번째 집까지 털었을때 최대값 - 2번째 집까지 털었을 때 최대값 vs 1번째 집까지 털었을 때 최대값 + 3번째 집을 털었을 때 값

4번째 집까지 털었을때 최대값 - 3번째 집까지 털었을 때 최대값 vs 2번째 집까지 털었을 때 최대값 + 4번째 집을 털었을 때 값

5번째 집까지 털었을때 최대값 - 4번째 집까지 털었을 때 최대값 vs 3번째 집까지 털었을 때 최대값 + 5번째 집을 털었을 때 값

...

 

이런식으로 규칙을 찾을 수 있다.

 

    public int rob(int[] nums) {        
        int[] memo = new int[nums.length + 1];
        
        if (nums.length < 3) {
            return Arrays.stream(nums).max().getAsInt();
        }
        
        memo[1] = nums[0];
        memo[2] = Math.max(nums[0], nums[1]);
        
        for (int i = 3; i <= nums.length; i++) {
            memo[i] = Math.max(memo[i - 1], memo[i - 2] + nums[i - 1]);
        }
        
        return Arrays.stream(memo).max().getAsInt();
    }

 

 

House Robber - LeetCode