[프로그래머스] 도둑질

문제

도둑질

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

 

 

 

풀이

설명

도둑이 훔칠 수 있는 돈의 최댓값을 구하는 문제입니다.

 

dp를 사용해 해결할 수 있습니다.

 

집이 원형으로 이어지기 때문에 첫 번째 집을 털면 마지막 집을 털 수 없습니다.

따라서 dp 배열 2개를 사용해 하나는 첫 번째 집을 털 때를, 다른 하나는 첫 번째 집을 털지 않을 때를 계산합니다.

 

dp[i]는 i번째 집까지 거쳤을 때 훔칠 수 있는 돈의 최댓값입니다.

 

점화식은 다음과 같습니다.

dp[i] = Math.max(dp[i - 2] + money[i], dp[i - 1])

 

예시 코드

function solution(money) {
  const n = money.length;
  // 첫 번째 집 포함
  const dp1 = Array(n).fill(0);
  // 첫 번째 집 미포함
  const dp2 = Array(n).fill(0);

  dp1[0] = money[0];
  dp1[1] = money[0];
  dp2[1] = money[1];

  for (let i = 2; i < n - 1; i++) {
    dp1[i] = Math.max(dp1[i - 2] + money[i], dp1[i - 1]);
  }
  for (let i = 2; i < n; i++) {
    dp2[i] = Math.max(dp2[i - 2] + money[i], dp2[i - 1]);
  }

  let max1 = 0;
  let max2 = 0;

  for (let i = 0; i < n; i++) {
    max1 = Math.max(max1, dp1[i]);
    max2 = Math.max(max2, dp2[i]);
  }

  return Math.max(max1, max2);
}