Leetcode 문제
이번에 풀어볼 문제는 리트코드 198번 문제 House Robber 다.
우선 문제를 살펴보자.
House Robber - LeetCode
Can you solve this real interview question? House Robber - 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 ho
leetcode.com
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.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 400
문제 설명
문제를 간략히 살펴보자. 우리는 여러 집들을 돌며 도둑질을 할 예정이다. 인풋으로 각 집들에서 훔칠 수 있는 돈이 주어진다. 한 가지 제한 조건은 만약 1번 집에서 돈을 훔쳤다면 바로 옆에 있는 2번 집에서 돈을 훔칠 수 없다는 것이다. 방법 시스템이 있어서 붙어있는 두 집을 연속으로 도둑질 할 경우 경찰에 리포트가 된다. 이때 경찰에 잡히지 않으면서 훔칠 수 있는 최대 금액은 얼마인지 계산하는 문제다.
문제 예시 1번처럼 4개의 집에서 훔칠 수 있는 돈이 [1,2,3,1]로 주어졌다. 1번 부터 4번 집까지 훔칠 수 있는 돈이 리스트로 주어졌다. 이때 제한 조건이 없다면 2번째 집과 3번째 집을 연속으로 도둑질해 5만큼의 돈을 얻을 수 있다. 하지만 문제의 조건에 따라 붙어있는 두 집을 연속으로 도둑질 할 수 없다. 따라서 이 경우 1번째 집과 3번째 집을 도둑질해 최대 4의 돈을 얻을 수 있다.
문제 자체가 불순한 의도를 가지고 있지만 문제는 문제로만 이해하도록 하자. 이제 문제를 풀어보자.
문제 접근법
이 문제를 해결하기 위해 우리는 dynamic programming을 이용할 것이다.
도둑이 여러 집 중 하나를 도둑질하고 있는 상황을 생각해 보자.
이 경우 도둑에게는 두 가지 경우의 수가 생긴다.
1) 현재 집을 도둑질한다.
이 경우 현재 집을 도둑질함으로서 얻을 있는 돈을 '전전' 집을 도둑질 했을때까지의 최대 수익에 더한다. 문제 조건에 따라 연속된 두 집을 도둑질 할 수 없기 때문이다.
2) 현재 집을 도둑질하지 않는다.
이 경우 최대 수익은 현재 집 바로 '전' 집을 도둑질 했을때까지의 최대 수익이 된다.
결국 이 두 가지 경우의 수를 비교해가며 최대 수익을 올릴 수 있는 경우를 계산해본다.
예를 들어 문제 예시 1번 [1,2,3,1]을 가지고 설명해 보자.
1) 첫번째 집
- 훔칠 경우 수익 = 1
- 훔치지 않을 경우 수익 = 0
따라서 우리가 첫번재 집에서 올릴 수 있는 최대 수익은 1이다.
이를 기억해 두기 위해 dp[0]=1로 기록해둔다.
여기서 0은 첫번째 집 인덱스 그리고 1은 최대 수익을 의미한다.
2) 두번째 집
- 훔칠 경우 수익 = 2
- 훔치지 않을 경우 수익 = 1
이 경우 홈칠 경우의 수익은 3이 아니라 2이다. 문제의 조건에 따라 연속된 두 집을 모두 훔칠 수 없기 때문이다.
따라서 첫번째 집 1과 두번째 집 2 중 수익이 더 큰 2가 최대 수익이 된다.
이를 기억해 두기 위해 dp[1] = max(1, 2) = 2로 기록해둔다.
3) 세번째 집
- 훔칠 경우 수익 = 4
- 훔치지 않을 경우 수익 = 2
이 경우 훔칠 경우 수익은 첫번째 집 1과 세번째 집 3의 합인 4가 된다.
두번째 집은 문제 조건에 따라 건너뛰었기 때문이다.
훔치지 않을 경우의 수익은 두번째 집 까지의 최대 수익이기 때문이 2가 된다.
이를 기억해 두기 위해 dp[2] = max(4, 2) = 4로 기록해 둔다.
4) 네번째 집
- 훔칠 경우 수익 = 3
- 훔치지 않을 경우 수익 = 4
이 경우 훔칠 경우의 수익은 두번째 집 2와 네번째 집 1의 합인 3이 된다.
훔치지 않을 경우 수익은 세번째 집까지의 최대 수익 4가 된다.
따라서 이를 기억해 두기 위해 dp[3] = max (3, 4) = 4
정리하자면 dp = [1, 2, 4, 4]가 된다.
따라서 얻을 수 있는 최대 수익은 dp에 저장된 마지막 element인 4가 된다.
이제 코드로 한 번 살펴보자.
문제 풀이
각 집마다 훔칠 수 있는 돈을 인풋으로 입력받기 위해 함수를 정의해 준다. (line 1)
만약 인풋이 없다면 0을 리턴하고 종료한다. (line 2)
집도 없고 훔칠 돈도 없다는 뜻이기 때문이다.
만약 인풋의 길이가 1이라면 집이 하나밖에 없다는 뜻이다.
이 경우 그 집에서 훔치는 것이 최대 수익이 되는 것이기 때문이 그 돈을 리턴하고 종료한다. (line 4-5)
앞서 설명했듯이 우리는 각 집을 도둑질 함에 있어 2가지 경우의 수가 있다.
그 2가지 경우의 수 중 더 큰 돈을 취할 때 그 돈을 기록해 두기 위해 0으로 초기화한 dp 배열을 하나 만들어 준다. (line 8)
그리고 초기 조건들을 dp에 넣어준다.
dp의 첫번째 인덱스는 첫번째 집에서 돈을 훔치는 경우다. (line 9)
그리고 dp의 두번째 인덱스는 첫번째 집의 돈과 두번째 집의 돈 중 더 큰 값이다 (line 10)
앞서 설명했듯이 붙어있는 두 집을 연속으로 도둑질 할 수 없기 때문이다.
세번째 집 부터는 for loop를 사용하여 탐색한다.
위에서 설명했듯이 세번째 집에서 도둑질을 하느냐 마느냐 2가지 경우의 수가 생긴다.
도둑질을 할 경우 첫번째 집에서 도둑질 함으로서 얻을 수 있는 최대 금액과 (=dp[i-2])
세번째 집에서 도둑질 함으로서 얻을 수 있는 금액 (=dp[i])의 합이 최대 금액이 된다.
반대로 세번째 집에서 도둑질을 하지 않을 경우 두번째 집 까지의 최대 금액 (=dp[i-1])이
지금까지 얻을 수 있는 최대 금액이 된다.
이 두 경우의 수 중 더 큰 금액을 취하는 것이 세번째 집 까지의 최대 금액이다. (line 14)
이 과정을 반복해 마지막 집까지 탐색을 하고 그때 얻을 수 있는 최대 수익을 dp에 저장한다.
그리고 최종적으로 dp에 저장된 마지막 element를 리턴하고 종료한다. (line 17)
우리는 모든 집들을 도둑질 해오면서 더 큰 값을 취해왔으므로 dp의 마지막에 element가 결국 최대 수익이 되기 때문이다.
문제 풀이 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
# Initialize an array to store the maximum amount of money that can be robbed up to each house
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
# For each house, compare the two choices: rob the current house or don't rob the current house
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
# The solution is the maximum amount of money that can be robbed up to the last house
return dp[-1]
# Test cases
print(rob([1,2,3,1])) # Output: 4
print(rob([2,7,9,3,1])) # Output: 12
|
cs |
관련 문제
리트코드 62번 Unique paths 문제 풀이 링크
리트코드 70번 Climing stairs 문제 풀이 링크
리트코드 139번 Work break problem 문제 풀이 링크
리트코드 213번 House robber II 문제 풀이 링크
리트코드 300번 Longest increasing subsequence 문제 풀이 링크
리트코드 322번 Coin change 문제 풀이 링크
리트코드 1143번 Largest Common Subsequence 문제 풀이 링크
'Leetcode > Dynamic Programming' 카테고리의 다른 글
| [Leetcode 아주 상세한 문제풀이] 300. Longest Increasing Subsequence – 코드 line 별 설명 (1) | 2023.12.25 |
|---|---|
| [Leetcode 아주 상세한 문제풀이] 213. House Robber II – 코드 line 별 설명 (1) | 2023.12.25 |
| [Leetcode 아주 상세한 문제풀이] 139. Word Break - 코드 line 별 설명 (1) | 2023.12.25 |
| [Leetcode 아주 상세한 문제풀이] 91. Decode Ways – 코드 line 별 설명 (1) | 2023.12.25 |
| [Leetcode 아주 상세한 문제풀이] 70. Climbing stairs - 코드 line 별 설명 (1) | 2023.12.25 |