[programmers/js] 도둑질

도둑질

https://school.programmers.co.kr/learn/courses/30/lessons/42897#

문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

풀이

1. 시작 index를 0, 1로 나눠서 들어간다.
2. 0번을 털면 마지막 집은 못 턴다.

function solution(money) {
    const len = money.length;
    
    let dp1 = Array(len).fill(0); // 처음 집을 턴다, 마지막 못 털어    
    dp1[0] = dp1[1] = money[0]
    
    for (let i = 2; i < len - 1; i++) {
        dp1[i] = Math.max(dp1[i - 2] + money[i], dp1[i - 1]);
    }
    
    let dp2 = Array(len).fill(0); // 2번 집부터 턴다.
    dp2[0] = 0;
    dp2[1] = money[1];
    for (let i = 2; i < len; i++) {
        dp2[i] = Math.max(dp2[i - 2] + money[i], dp2[i - 1]);
    }
    return Math.max(dp1[len-2], dp2[len-1]);
}