[Medium] 198. 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 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

 

해결 과정

인접한 집을 털지 않고 최대로 훔칠 수 있는 돈의 수를 계산하는 문제였다.

첫 시도는 index를 2n - 1, 2n 으로 나누어서 홀수 인덱스, 짝수 인덱스를 나누어 해보았다. 절반 정도는 pass가 됐지만, 두 칸 이상 떨어져 있는 집을 방문한다면 이런 알고리즘으로는 해결할 수 없었다...

결국 다른 방법을 시도해야했다.

 

전에 사용했던 피보나치 수열 방법으로 해결해보았다. 

다음 트리로 이동을 하면서 현재 위치의 값을 선택할 것인지, 지금까지 더한 값을 선택할 것인지 Math.max() 로 최대값을 구한다. 

이전 문제보다 난의도가 있는 문제라 100% 이해하기 어려웠다...

DP도 익숙해지는 날이 오길 바란다.

 

해결 코드

첫 시도

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    
    let oddMoney = 0;
    let evenMoney = 0;
    
    // 홀수 index 일 때
    for(let i = 0 ; i < nums.length / 2 ; i++){
        let index = 2 * i + 1;
        if(nums[index] !== undefined){
            oddMoney += nums[index];
        
            console.log('index : ' + index);
            console.log('oddMoney : ' + oddMoney);
        }
    }
    
    // 짝수 index 일 때
    for(let i = 0 ; i < nums.length / 2 ; i++){
        let index = 2 * i;
        evenMoney += nums[index];
        
        console.log('index : ' + index);
        console.log('evenMoney : ' + evenMoney);
    }
    
    return oddMoney > evenMoney ? oddMoney : evenMoney;
};

 

두번째 시도

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (nums.length == 0) return 0;
    let prev1 = 0,
        prev2 = 0;
    
    // [prev2, prev1, num, num + 1, ...]
    for (let num of nums) {
        let tmp = prev1;
        prev1 = Math.max(prev2 + num, prev1);
        prev2 = tmp;
    }
    
    return prev1;
};

---

참고 사이트

https://leetcode.com/problems/house-robber/discuss/156523/From-good-to-great.-How-to-approach-most-of-DP-problems.

From good to great. How to approach most of DP problems. - LeetCode Discuss

 

https://www.youtube.com/watch?v=73r3KWiEvyk