DaleStudy | Leetcode Study 1주차 - House Robber

Leetcode Study

문제

You are a professional robber planning to rob houses along a street. Each houst has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houst have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

 

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

 

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

 

풀이

 

DP(Dynamic Programming)는 복잡한 문제를 여러 하위 문제로 나누고, 이전 결과를 저장해서 중복 계산을 피하는 최적화 기법입니다.
일반적으로는 최대값/최소값, 개수 세기, 경로 탐색과 같은 문제에서 많이 사용되며,

예를 들어 “근접한 항목을 선택하지 않고 최대 합을 구하는 문제”처럼 결정 간 제약 조건이 있는 문제에도 자주 사용됩니다.

 

먼저 알고리즘 문제를 풀 때는 문제를 단계별로 어떻게 풀 건지 설계하는게 중요한데, 이 문제는 3부분으로 나눠서 볼 수 있습니다. 

1. 주어진 배열과 동일한 크기를 가진 배열을 생성합니다.
2. 그 배열에는 인접하지 않은 원소를 더한 값과 이전의 인덱스의 값 중 큰 값을 비교해서 큰 값을 추가합니다. 
3. 배열의 마지막 원소를 리턴하면 됩니다. 

function rob(nums: number[]): number {
    if (nums.length === 0) { return 0; }
    if (nums.length === 1) { return nums[0]; }

    const maxSums = nums.slice();
    maxSums[1] = Math.max(nums[0], nums[1]);

    for(let i=2; i<nums.length; i++) {
        maxSums[i] = Math.max(maxSums[i-1], (maxSums[i-2] + nums[i]))
    }

    return maxSums[maxSums.length - 1]
};

 

 

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