198. House Robber

늘보·2021년 11월 9일

LeetCode

목록 보기

68/69

💡 풀이

var rob = function (nums) {
  let dp = [];

  if (nums.length === 1) return nums[0];

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

  for (let i = 2; i < nums.length; i++) {
    // i번째 집을 털었을 때 가질 수 있는 돈의 최댓값 = dp[i]
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }

  // console.log(dp);
  return dp[dp.length - 1];
};

📝 정리

기본 DP 문제로 볼 수 있다. DP 말고 다른 방법 중에 greedy..? swap? two pointers? 아직 내가 정확하게 이해를 하지 못한 방법이 하나 더 있는데 (더 간단하다) 그 방법은 아직 이해가 덜 됐기 때문에 여기서는 작성하지 않았다.

문제 요구사항을 보자. 당신은 도둑이다. 인접한 집의 돈을 도둑질하면 경찰에 신고하기 때문에 경찰에 신고당하지 않는 선에서 당신이 가장 많은 돈을 도둑질 했을 때 그 액수는 얼마인가? 라고 묻는 것이다. 풀이는 다음과 같다.

최댓값을 담을 dp 배열의 첫번째 인덱스는 다음과 같이 정한다. dp[0] = nums[0];
i번째 집을 털었을 때 가질 수 있는 돈의 최댓값 = dp[i]가 된다.
이를 생각해보면, 인접 집은 도둑질을 할 수 없으니, dp[i - 1], dp[i - 2] + nums[i], 즉 dp[i-1]과 dp[i-2] + nums[i] 중 더 큰 값이 최댓값이 된다.