[리트코드] 198. House Robber - js

1. 문제

https://leetcode.com/problems/house-robber/description/

House Robber - LeetCode

2. 코드

원래 작성한 코드)

당연한 오답.. 무조건 하나 건너 하나 선택한다는 보장이 없다.

var rob = function(nums) {
    let odd = nums.filter((el,idx) => (idx % 2)).reduce((a,c) => a += c,0);
    let even = nums.filter((el,idx) => !(idx % 2)).reduce((a,c) => a += c,0);

    return odd > even ? odd : even;
};

정답)

nums =[2,1,1,2] 라면? 2와 2를 선택하는게 이득이다. 우리가 궁금한건 현재 인덱스 이전까지의 누적합 중 큰 값이다.

let maxAtOneBefore = Math.max(nums[0], nums[1]);

위 코드를 통해 애초에 0번, 1번 인덱스 값 중 큰 값을 선택하고 시작할 수 있다. 그래서 마지막 인덱스 값인 2에 도달했을 때, 

const maxAtCurrent = Math.max(nums[i] + maxAtTwoBefore, maxAtOneBefore);

Math.max(2 + 2 , 3); 이 되어 정답 4를 리턴할 수 있다.

만약 let maxAtOneBefore = nums[1]; 로 작성했다면 죽이되나 밥이되나 1번째 인덱스 값인 1을 안고갈 수 밖에 없고, 이렇게 되면 최대값을 리턴할 수 없게된다.

/**
 * @param {number[]} nums
 * @return {number}
 */

var rob = function(nums) {
    if (!nums.length) return 0;
    if (nums.length === 1) return nums[0];
    
    let maxAtTwoBefore = nums[0];
    let maxAtOneBefore = Math.max(nums[0], nums[1]);
    
    for (let i = 2; i < nums.length; i++) {
        const maxAtCurrent = Math.max(nums[i] + maxAtTwoBefore, maxAtOneBefore);
        
        maxAtTwoBefore = maxAtOneBefore;
        maxAtOneBefore = maxAtCurrent;
    }
    
    return maxAtOneBefore;
};