프로그래머스 [Lv. 4] 도둑질 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(money) {
    const lenM = money.length;
    let dp = Array(2).fill().map(() => Array(lenM).fill(0));
    dp[0][0] = money[0];
    dp[0][1] = Math.max(money[0], money[1]);
    dp[1][1] = money[1];
    for (let idx = 2; idx < lenM-1; idx++) {
        dp[0][idx] = Math.max(dp[0][idx-1], dp[0][idx-2]+money[idx]);
        dp[1][idx] = Math.max(dp[1][idx-1], dp[1][idx-2]+money[idx]);
    }
    dp[1][lenM-1] = Math.max(dp[1][lenM-2], dp[1][lenM-3]+money[lenM-1])
    const answer = Math.max(dp[0][lenM-2], dp[1][lenM-1]);
    return answer;
}

풀이 방법

1. 0으로 채워진 배열 2개를 만든다.
   1. dp[0]은 마지막 집을 방문하지 않는다.
   2. dp[1]은 마지막 집을 방문한다.
2. dp[0]은 마지막 집을 방문하지 않으니 첫 번째 집부터 최대값을 저장해주면서 lenM-2번째까지 메모이제이션을 진행한다.
3. dp[1]은 첫번째 집을 방문하지 않아야 마지막 집을 방문할 수 있으므로 lenM-1까지 진행한다.
4. 결과적으로 dp[0][lenM-2]와 dp[1][lenM-1]을 비교하고 큰 수를 return한다.

느낀점

• 기본 개념은 잡혔지만 단순하게 원형으로 집이 되어있다는 사실을 망각해서 계속 틀렸다.
• 특히 [1, 2, 3] 이게 4 아니야? 라는 생각때문에 풀지 못했고 1을 방문하면 3을 방문하지 못하기 때문에 답은 3이 나오게 된다.