198. House Robber

문제

https://leetcode.com/problems/house-robber/description/

도둑이 집을 털려고 한다. 인접해 있는 연속된 집을 털면 경찰에 발각된다. 각 집에 있는 돈이 담긴 배열인 nums 가 주어졌을 때 도둑이 경찰에게 걸리지 않고 오늘 밤에 털 수 있는 최대 금액을 구하는 문제

풀이

아이디어

어떤 집을 턴다고 했을 때 최대 금액을 구하는 식은 아래와 같이 세울 수 있다.: Math.max(전 집을 털었을 때의 최대 금액, 전전 집을 털었을 때의 최대 금액 + 지금 집을 털었을 때 얻는 금액) 점화식을 세웠으니… Dynamic Programming으로 푼다. 연산 횟수를 줄여주기 위해서 메모 배열을 이용했다.

코드

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)**이 된다.