LeetCode - 198. House Robber

[LeetCode] 198. House Robber

LeetCode 198번 문제를 풀어보았다.. Link

Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Intuition

문제에 주어진 Constraint를 잘 고려해야하는 문제였다.

처음에는 DFS로 풀어야하나 고민했었던 문제..

허나 DFS로 접근할 경우 쓸 때 없는 반복이 많아질 수 있고, 순서 상관없이 도둑질 할 집을 고르면 되는 문제이기 때문에 적절치 않았다.

Brute Force로 모든 케이스를 보는 방법도 있겠지만 집의 개수가 많아질수록 계산량이 엄청나게 커지기 때문에 최적화 방법을 생각해내야했다.

• 첫번째 집을 턴다고 할 때 두번째 집을 제외한 나머지 집을 털 수 있기 때문에 Decision Tree처럼 가지를 펼치면서 계속 계산해나가는 방법?

위에서 말한 것 처럼 트리를 확장해나가는 방식으로 할 때, 잘 생각해보면 조건에 부합하는 집을 선택하는 것과, 또다시 그 집을 제외한 나머지 집을 턴다고 했을 때 그 최대값을 찾아나가는 과정이 반복되고 있다.

즉 경찰에 걸리지 않고 훔칠 수 있는 최대 금액을 찾는 커다란 문제는 조건에 부합하는 집을 선택하고 또 나머지 집들중 조건에 부합하는 집을 선택한다음 그들중에 최대값을 찾아가는 문제들로 쪼개서 생각할 수 있다는 것이다.

-> Dynamic Programming 을 쓰는것이 적절하다.

Approach

1. dp dp를 생성, dp의 index는 방의 개수를 의미
2. 방의 개수가 i일때 dp[i-1]과 dp[i-2] + room[i]를 비교
3. 둘 중 더 큰 수를 dp[i]에 대입
4. 2~3을 방의 개수만큼 반복

Complexity

• Time complexity:

  집의 개수를 n이라고 할 때, \(O(n)\)

• Space complexity: \(O(n+1) = O(n)\)

My Code

class Solution:
   def rob(self, nums):
	dp = [0] * (len(nums) + 1)
	dp[1] = nums[0]
	for i in range(2, len(nums)+1):
		dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
	return dp[-1]

공간복잡도를 줄이고 \(O(1)\)로 줄이고싶다면 DP Table을 굳이 만들어서 쓸 필요없이 Temp 변수를 만들어서 최대값을 계속해서 Update해나가는 방식을 쓰면 된다.