IT/알고리즘
LeetCode 198. House Robber
thesse
2023. 5. 22. 00:11
300x250
반응형
https://leetcode.com/problems/house-robber/
Dynamic Programming 활용 문제
난이도 : medium
* IT's LIT 3주차
class Solution {
/* Runtime: 0 ms, Memory: 40.1 MB */
public int rob(int[] nums) {
// 각 소문제별 해를 저장할 어레이
int[] max = new int[nums.length];
// 1채, 2채까지는 단순 계산
if(nums.length == 1) {
return nums[0];
}
max[0] = nums[0];
max[1] = Math.max(max[0], nums[1]);
if(nums.length == 2) {
return max[1];
}
// 집이 3채인 경우부터 반복문 돌리기
for(int i=2; i<nums.length; i++){
max[i] = Math.max(nums[i]+max[i-2], max[i-1]);
}
return max[nums.length-1];
}
}
소문제 나누는법
n번째 집을 터느냐 마느냐를 기준으로
- n번째 집을 털거면 이웃한 집을 제외한 n-2부터 0까지의 집 중에서 최대값과 n번째 집의 값을 더하고
- n번째 집을 안털거면 이웃한 집을 털수 있으므로 n-1부터 0까지의 집 중에서 최대값을 비교해서
더 큰거 고르기
* 참고
NeetCode 영상
https://www.youtube.com/watch?v=73r3KWiEvyk
300x250
반응형