<Medium>House Robber II (LeetCode : C#)

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

📕 문제 설명

원형으로 배치된 집들이 있다. 인접한 집들에는 보안 시스템이 있으며, 같은 날 인접한 두 집이 털리면 경찰에 자동적으로 연락한다. 집마다 돈을 나타내는 정수 배열이 주어질 때 경찰에게 알림을 보내지 않고 최대한으로 얻을 수 있는 돈 반환

• Input
  정수 배열
• Output
  경찰에게 알리지 않고 최대한 가져올 수 있는 돈 (즉, 인접한 두 집을 가져오지 않으면서 최대로 가져올 수 있는 돈)

예제

풀이

이거 백준에서 와인 마시기인가? 되게 비슷한 문제 있었던 것 같다. 유명한 dp 문제.

memo 사용해서 풀었다. 핵심은 1번째 집을 포함하느냐 안하느냐이다. 원형으로 이루어져있기 때문에 첫집과 마지막집 처리만 잘해주면 점화식 자체는 쉬운 문제이다.
(현재거 포함하고 인접한집 건너뛴 집의 max money와 이전 인접한 집의 max money 중 더 큰 것 가져오는 것이 점화식)

public class Solution {
    public int Rob(int[] nums) { 
        int n = nums.Length;  
        if (n <= 3) return nums.Max();

        int[] maxMoney1 = new int[n];
        int[] maxMoney2 = new int[n];
        maxMoney1[0] = nums[0];
        maxMoney1[1] = Math.Max(nums[0], nums[1]);
        maxMoney2[0] = 0;
        maxMoney2[1] = nums[1];

        for (int i = 2; i < n; i++)
        {
            maxMoney1[i] = Math.Max(nums[i] + maxMoney1[i-2], maxMoney1[i-1]);
            maxMoney2[i] = Math.Max(nums[i] + maxMoney2[i-2], maxMoney2[i-1]);
        }
        
        return Math.Max(maxMoney1[n-2], maxMoney2[n-1]);
    }
}

결과