Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 밥먹고
- 눈알빠지겠네
- 하스스톤
- 코딩테스트
- 게임
- 메탈퍼즐
- 천등
- 나쫌
- 맛집
- DIY
- 잠실새내
- 토이프로젝트
- 누룽지소금빵
- 메일우유
- 취미
- 발더스게이트
- LeetCode
- 알고리즘테스트
- javascript
- 코테
- 발더스모드
- 송리단
- 3d퍼즐
- 버즈2프로
- 노노그램
- 미앤아이
- 뜨아거
- 바질토마토뭐시기
- 서울제빵소
- 발더스3
Archives
- Today
- Total
.Zzumbong
[leetCode/JS] 198. House Robber 본문
난이도 [ 🤔 ] Medium
문제 설명
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.
난 프로페셔널 도둑이다.
각 집에 있는 돈이 array nums로 입력되는데, 근접한 집을 털면 안된다.
최대한 털 수 있는 돈은 얼마인가?
입출력 예
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
내 솔루션
- 뭔가 조건이 있으면서 최대 얼마인가? 최소 얼마인가? 하면 DP부터 생각해야하더라.. 어렵
- 만약 [3, 1, 1, 9] 라면 첫집은 3을 골라야한다. 그러므로 첫 집은 Math.max(nums[0], nums[1])로 고른다.
- Math.max(nuns[i-2] + nums[i], nums[i-1]) 로 지금 집 + 이전이전집 or 이전집 중 고르는 것이 기본룰이다.
- 맨 처음 if에서 length가 1 또는 2는 그냥 큰 값을 리턴하면 된다.
var rob = function(nums) {
if(nums.length < 3) return Math.max(...nums);
let prevPrev = nums[0];
let prev = Math.max(nums[1], nums[0]);
for(let i = 2; i < nums.length; i++) {
const max = Math.max(nums[i] + prevPrev, prev);
prevPrev = prev;
prev = max;
}
return prev
};
감상평
- DP가 약점인 것이 분명하다. DP 같은데 하면서 어떻게 만들지~ 가지고 30분 내내 씨름했다.
- 결국 혼자서 풀기는 포기하고 DP 알고리즘 구글링하며 혼자 생쇼를 했다.
- 하루 종일 걸리뻔했다. 쥐엔장
- DP문제를 하나 더 풀어보자.
'coding test > leetCode' 카테고리의 다른 글
[leetCode/JS] 1143. Longest Common Subsequence (0) | 2022.12.15 |
---|---|
[leetCode/JS] 152. Maximum Product Subarray (0) | 2022.12.14 |
[leetCode/JS] 931. Minimum Falling Path Sum (0) | 2022.12.13 |
[leetCode/JS] 70. Climbing Stairs (0) | 2022.12.12 |
[leetCode/JS] 124. Binary Tree Maximum Path Sum (0) | 2022.12.11 |
Comments