213. House Robber II
https://leetcode.com/problems/house-robber-ii/
I. 문제 개요
DP를 활용하여 도둑질로 얻을 수 있는 최댓값을 구하는 문제이다.
II. 알고리즘 설계
만약 첫번째 집을 털면 2번째, 마지막 집은 털 수 없다.
왜냐하면 집들은 원형으로 놓여있기에, 첫번째 집을 털면 2번째와 마지막 집에 경보가 들어오기 때문이다.
따라서, 첫번째 집을 터는 경우와 털지 않는 경우 2가지로 나눠서 생각해야 한다.
1. 첫번째 집부터 터는 경우
| V(시작) | X | O | ... | O | X |
V: 시작점
O: 털 수 있는 집
X: 못 터는 집
dp에 사용할 list를 만들고, 1번째와 2번째 원소는 nums[0]으로 변경한다.
그다음 2번째 집부터 터는 경우와, 털지 않았을 때의 금액 중, 더 큰 값을 list에 집어넣는다
2. 2번째 집부터 터는 경우
| X | V | X | O | ... | O |
여기에 사용할 list를 만들고, 2번째와 3번째 원소는 nums[1]으로 변경한다.
그다음 3번째 집부터 터는 경우와, 털지 않았을 때의 금액을 비교하여, 더 큰 값을 list에 집어넣는다.
dp[i]는 i번째 집까지 왔을 때, 털 수 있는 금액의 최댓값을 나타낸다.
III. 문제 풀이
1. 집들의 개수가 적을 경우
if len(nums) == 1:
return nums[0]
elif len(nums) <= 3:
return max(nums)
집이 3개 이하라면, 바로 최댓값을 반환하면 된다.
집이 3개인 경우, 어떤 집을 털어도 나머지 두 집에는 경보가 울려, 털 수 없게 된다.
2. DP 탐색
1) 변수 초기화
n = len(nums)
dp1 = [0 for _ in range(n)] # 1번 집 털기
dp2 = [0 for _ in range(n)] # 2번 집 털기
dp1[0] = nums[0]
dp2[1] = nums[1]
첫번째 집을 터는 경우와, 2번째 집부터 터는 경우 각각에 사용할 list를 만들어준다.
첫번째 집을 털 때, dp1의 맨 앞 원소는 nums[0]으로 초기화한다.
2번째 집부터 터는 경우, dp2의 2번째 원소는 nums[1]으로 값을 바꿔준다.
2) 1번째 집부터 털 때
for i in range(1, n-1):
not_rob = dp1[i-1] # 현재 집을 털지 않을 때 얻는 돈
rob = dp1[i-2] + nums[i] # 현재 집을 털 때 얻는 돈
dp1[i] = max(rob, not_rob) # 최댓값을 dp1에 반영
2번째 집부터 살펴보기 시작한다.
현재 집을 털 때 얻을 수 있는 최댓값은, 2칸 앞의 집을 턴 경우 얻는 돈과 현재 집의 돈을 합한 값이다.
털지 않는다면, 1칸 앞의 집을 털었을 때 얻는 돈을 그대로 가져간다.
dp1[i] 에는, 위의 두 값 중 최댓값을 집어넣는다.
3) 2번째 집부터 털 때
for i in range(2, n):
not_rob = dp2[i-1] # 현재 집을 털지 않을 때 얻는 돈
rob = dp2[i-2] + nums[i] # 현재 집을 털 때 얻는 돈
dp2[i] = max(rob, not_rob) # 최댓값을 dp2에 반영
여기서는 3번째 집부터 살펴본다.
현재 집을 털지 않는다면, 1칸 전의 집을 털었을 때 얻는 돈을 그대로 가져간다.
만약 턴다면, 2칸 앞에 있는 집을 털어서 나온 돈과, 현재 집을 털 때 얻는 돈을 합한 만큼을 가져갈 수 있다.
이 두 경우 중, 더 큰 값을 dp2[i]에 집어넣는다.
4) 답 구하기
fst = max(dp1) # 1번째 집부터 털 때 올릴 수 있는 최대 성과
sec = max(dp2) # 2번째 집부터 털 때 올릴 수 있는 최대 성과
ans = max(fst, sec) # 더 큰 값을 반환
return ans
첫번째 집을 털 경우와, 털지 않은 경우별로 얻을 수 있는 최댓값을 구한다.
여기서 경우별로 나온 최댓값들을 비교하여, 더 큰 값을 정답으로 반환한다.
IV. 전체 코드
class Solution:
def rob(self, nums: List[int]) -> int:
# 1. 집들의 개수가 적을 경우
if len(nums) == 1:
return nums[0]
elif len(nums) <= 3:
return max(nums)
# 2. DP 탐색
else:
# 1) 변수 초기화
n = len(nums)
dp1 = [0 for _ in range(n)] # 1번 집 털기
dp2 = [0 for _ in range(n)] # 2번 집 털기
dp1[0] = nums[0]
dp2[1] = nums[1]
# 2) 1번째 집부터 털 때
for i in range(1, n-1):
not_rob = dp1[i-1] # 현재 집을 털지 않을 때 얻는 돈
rob = dp1[i-2] + nums[i] # 현재 집을 털 때 얻는 돈
dp1[i] = max(rob, not_rob) # 최댓값을 dp1에 반영
# 3) 2번째 집부터 털 때
for i in range(2, n):
not_rob = dp2[i-1] # 현재 집을 털지 않을 때 얻는 돈
rob = dp2[i-2] + nums[i] # 현재 집을 털 때 얻는 돈
dp2[i] = max(rob, not_rob) # 최댓값을 dp2에 반영
# 4) 답 구하기
fst = max(dp1) # 1번째 집부터 털 때 올릴 수 있는 최대 성과
sec = max(dp2) # 2번째 집부터 털 때 올릴 수 있는 최대 성과
ans = max(fst, sec) # 더 큰 값을 반환
return ans
V. 풀이 결과
