> [!date] published: 2025-04-04 ## 문제 [House Robber - LeetCode](https://leetcode.com/problems/house-robber/description/) 도둑이 집을 털려고 한다. 인접해 있는 연속된 집을 털면 경찰에 발각된다. 각 집에 있는 돈이 담긴 배열인 `nums` 가 주어졌을 때 도둑이 경찰에게 걸리지 않고 오늘 밤에 털 수 있는 최대 금액을 구하는 문제 ## 풀이 ### 아이디어 어떤 집을 턴다고 했을 때 최대 금액을 구하는 식은 아래와 같이 세울 수 있다.: Math.max(전 집을 털었을 때의 최대 금액, 전전 집을 털었을 때의 최대 금액 + 지금 집을 털었을 때 얻는 금액) 점화식을 세웠으니… **Dynamic Programming**으로 푼다. 연산 횟수를 줄여주기 위해서 메모 배열을 이용했다. ### 코드 ```typescript function rob(nums: number[]): number { const n = nums.length; if (n === 1) { return nums[0]; } // idx 집을 터는 경우 vs 안 터는 경우를 비교해서 큰 값을 저장하는 dp 배열 const memo = new Array(n).fill(0); memo[0] = nums[0]; memo[1] = Math.max(memo[0], nums[1]); for (let idx = 2; idx < n; idx++) { // idx번째 집에서의 최대 금액 = idx번째 집을 터는 경우 vs 안 터는 경우 중 최댓값 memo[idx] = Math.max(memo[idx - 2] + nums[idx], memo[idx - 1]); } return memo[n - 1]; } ``` ### 시간 / 공간 복잡도 for loop 에서 nums 배열의 각 원소에 한번씩만 접근하므로 **시간 복잡도**는 **O(n)** 이 된다. n만큼의 배열을 만들기 때문에 **공간 복잡도** 역시 **O(n)** 이 된다.