[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문제를 하나 더 풀어보자.