[LeetCode] House Robber

https://leetcode.com/problems/house-robber/description/?envType=study-plan-v2&envId=leetcode-75

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

---

어떤 거리에 있는 집에 있는 현금을 나타내는 숫자 배열이 주어진다.

인접한 집을 털 수 없다고 했을 때, 가장 많은 돈을 털 수 있는 액수를 리턴한다.

 

즉ㅋㅋ 숫자가 들어 있는 배열이 주어 지고,

서로 인접하지 않은 숫자를 더해서 나올 수 있는 가장 큰 값을 구하는 문제.

 

문제 자체는 심플하다.

var rob = function(nums) {
    let odd = 0;
    let even = 0;

    for(let i=0; i < nums.length; i++){
        if(i % 2 == 0){
            even += nums[i];
        }else{
            odd += nums[i];
        }
    }

    return Math.max(even, odd);
};

 

그냥 건너뛰는 것보다는 그래도 털고 넘어가는게 이득이라고 생각해서

단순히 그냥.. 홀수자리, 짝수자리 각각 더해서 더 큰걸로 제출했는데, 대부분의 결과는 다 통과가 되더라.

하지만 [2, 1, 1, 2] 라던가 [1, 3, 1, 3, 100] 같은 테스트케이스는 통과할 수 없다.

사실 당연히 그렇다. "인접한" 집을 못 털 뿐이지, 두 번 이상 건너의 집도 털 수 없다는 조건은 없으니까.

 

var rob = function(nums) {
    if(nums.length == 0){
        return 0;
    }
    if(nums.length == 1){
        return nums[0];
    }
    let robIfRobbed = 0;
    let robIfSkipped  = 0;
    let curr = 0;
    for(let i=0; i < nums.length; i++){
        curr = robIfSkipped + nums[i];
        robIfSkipped = Math.max(robIfRobbed, robIfSkipped);
        robIfRobbed = curr;
    }
    return Math.max(robIfSkipped, robIfRobbed);
};

 

그래서 고친 게 이것... 겸사겸사 배열 길이 0이랑 1일 때 걸러도 주고.

이번 집을 털기 위해서는, 이전 집을 털지 않았어야 한다. 

그렇기 때문에 이번 집을 턴 결과 curr은 이전에 건너뛰었을 때의 값에 현재 집의 돈을 더한다.

이전에 건너뛰었을 때의 값은 어쨌든 이전에 건너뛰었든, 털었든 상관없이 현재까지 턴 가장 큰 금액이 들어간다.

그리고 curr은 이번에 턴 경우의 총 금액이므로 마지막에 robIfRobbed에 값을 업데이트해준다.

마지막으로, 결국 robIfSkipped와 robIfRobbed를 비교해서 더 큰 값을 리턴하면 된다.

 

예시로, [2,1,1,2] 를 돌려 보면 아래처럼 진행된다.

 

i	curr	robIfSkipped	robIfRobbed
0	0 + 2	0	2
1	0 + 1	2	1
2	2 + 1	2	3
3	2 + 2	3	4

 

주어진 테스트케이스 중에 [0, 0] 이런 것도 있었는데ㅋㅋㅋ

이와 관련해서 discussion 에서 본 웃긴 댓글...