[LeetCode] 198. House Robber - Java

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

House Robber - LeetCode

---

문제

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses 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

---

풀이

풀이 과정

각 집마다 흠칠 수 있는 최대 금액이 원소로 담겨있는 배열 nums가 주어진다.
하루에 연속해있는 두 집을 터는 경우에는 경보장치가 작동하여 경찰이 출동하게된다. 이 때 강도가 하루에 털 수 있는 최대 금액을 구하는 문제이다.

첫 번째 집부터 마지막 집까지 차례대로 탐색할 때 각 집에서 생각할 수 있는 경우의 수는 두 가지로 볼 수 있다.

1. 현재 집에서 훔칠 수 있는 금액과 두 번째 전 집까지 훔친 금액의 합
2. 현재 집은 털지 않고 이전 집 까지 훔친 금액

두 가지 경우를 탐색하여 각 집마다 최대 금액을 저장해두고 마지막까지 탐색한 결과값을 구한다.

 

우선 nums 배열의 길이가 1인 경우 탐색이 불필요하므로 해당 값을 바로 반환한다.

// nums의 원소가 한개인 경우 해당값을 반환
if(nums.length == 1) return nums[0];

 

다음으로 탐색한 결과값을 저장할 배열을 선언하고
첫 번째 집까지 훔칠 수 있는 최대값은 첫 번째 집의 금액 뿐이므로 첫 번째 인덱스는 nums 배열의 첫 번째 값으로 초기화,
두 번째 집까지 훔칠 수 있는 최대값은 첫 번째 집의 금액이거나 두 번째 집의 금액이므로 두 번째 인덱스는 nums 배열의 첫 번째 값과 두 번째 값 중 큰 값으로 초기화한다.

// 탐색한 결과값을 저장할 배열
int[] dp = new int[nums.length];

// 첫 번째 집은 첫 번째 집의 가격으로 초기화
dp[0] = nums[0];
// 두 번째 집은 첫 번째 집과 두 번째 집 중 높은 가격으로 초기화
dp[1] = Math.max(nums[0], nums[1]);

 

남은 원소들을 순회하며 위에서 정의한 두가지 경우의 수를 판단하며 값을 탐색하고 마지막까지 탐색한 결과값을 최종 반환한다.

// 남은 집들을 순회하며 탐색
for(int i = 2; i < nums.length; i++){
    // n번째 집에서 탐색할 수 있는 경우는 두 가지
    // 1. n - 2번째 집까지의 최대 금액과 n번째 집 금액의 합
    // 2. n - 1번째 집까지의 최대 금액
    // 두 가지 경우 중 더 큰 값을 n에 저장한다.

    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}

// 마지막까지 탐색한 결과값을 반환
return dp[nums.length - 1];

---

최종 코드

class Solution {
    public int rob(int[] nums) {
        // nums의 원소가 한개인 경우 해당값을 반환
        if(nums.length == 1) return nums[0];

        // 탐색한 결과값을 저장할 배열
        int[] dp = new int[nums.length];

        // 첫 번째 집은 첫 번째 집의 가격으로 초기화
        dp[0] = nums[0];
        // 두 번째 집은 첫 번째 집과 두 번째 집 중 높은 가격으로 초기화
        dp[1] = Math.max(nums[0], nums[1]);

        // 남은 집들을 순회하며 탐색
        for(int i = 2; i < nums.length; i++){
            // n번째 집에서 탐색할 수 있는 경우는 두 가지
            // 1. n - 2번째 집까지의 최대 금액과 n번째 집 금액의 합
            // 2. n - 1번째 집까지의 최대 금액
            // 두 가지 경우 중 더 큰 값을 n에 저장한다.

            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        // 마지막 까지 탐색한 결과값을 반환
        return dp[nums.length - 1];
    }
}

---