[LeetCode] 213. House Robber II - Java

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

---

문제

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system 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 = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

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 3:

Input: nums = [1,2,3]
Output: 3

 

Constraints:

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

---

풀이

풀이 과정

LeetCode의 198번 House Robber와 거의 같은 문제이다.
https://hyojun.tistory.com/entry/LeetCode-198-House-Robber-Java

[LeetCode] 198. House Robber - Java

 

주어진 nums 배열의 원소들은 각각 집에서 훔칠 수 있는 금액이고 인접해 있는 집을 동시에 털 경우 경찰이 출동하게 된다.
여기서 House Robber 문제와 다른점은 첫 번째 집과 마지막 집을 인접해 있다고 보는 것이다.

첫 번째 집과 마지막 집이 인접해 있다고 할 때, 첫 번째 집을 들른 경우 마지막 집은 탐색할 필요가 없고 두 번째 집을 들른 경우 마지막 집까지 탐색이 필요하다.

따라서 탐색값을 저장할 dp배열 두 개를 만들고 첫 번째 집을 들르는 경우와 두 번째 집을 들르는 경우를 각각 탐색해 두 탐색 결과 중 더 큰 값을 반환한다.

---

최종 코드

class Solution {
    public int rob(int[] nums) {
        // nums의 원소가 한 개일 경우 해당 원소를 바로 return
        if(nums.length == 1) return nums[0];

        // 첫 번째 집을 들르는 경우
        int[] dp1 = new int[nums.length];
        // 두 번째 집을 들르는 경우
        int[] dp2 = new int[nums.length];
        
        dp1[0] = dp1[1] = nums[0];
        dp2[1] = nums[1];
        
        for(int i = 2; i < nums.length; i++) {
            if(i < nums.length - 1) {
                // dp1은 마지막 집 전까지만 탐색
                dp1[i] = Math.max(dp1[i-2] + nums[i], dp1[i-1]);                
            }
            // dp2는 마지막 집까지 탐색
            dp2[i] = Math.max(dp2[i-2] + nums[i], dp2[i-1]);
        }
        
        // 두 개의 최종 탐색값중 큰 값을 return
        return Math.max(dp1[nums.length - 2], dp2[nums.length - 1]);
    }
}

---