[프로그래머스] Lv4. 도둑질 - JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 4

출처 : 프로그래머스 - 도둑질

문제

제한사항

📌 내가 생각한 풀이

DP를 활용하는 문제이다. 여기서 핵심은 첫번째 집을 털었을 경우와 털지않고 두번째 집을 털었을 경우를 구분하여 Dp배열을 만들고 그 중 최대값을 구하자. 단, 첫번째 집을 털었을땐 마지막집을 털지못하는 점을 명심하자!

function solution(money) {
    var answer = 0;
    let len = money.length;
    let dp1 = new Array(len).fill(0);
    let dp2 = new Array(len).fill(0);
    dp1[0] = money[0];
    dp1[1] = money[0];
    dp2[1] = money[1];
    for(var i = 2; i<money.length-1; i++){
        dp1[i] = Math.max(dp1[i-1], dp1[i-2]+money[i]);
    }
    for(var i = 2; i<money.length; i++){
        dp2[i] = Math.max(dp2[i-1], dp2[i-2]+money[i]);
    }

    return Math.max(dp1[len-2], dp2[len-1])
    
}

📌 느낀점

스티커붙히기 문제와 매우 유사한 문제였다. LV4 단계 문제지만 비교적 쉬운 DP문제였다.