House Robber II

요즘 DP 문제들을 하나씩 정복해 나가는 중이다. 먼저 가장 쉬운 1D 배열에 디피를 마스터하고 그 다음에 2D 배열 디피 그리고 그래프 디피를 마스터할 생각이다. 프리미엄 계정도 생각 중...일단 하루에 2문제 혹은 3문제 풀 생각이었는데 생각보다 진행 속도가 느려서 걱정이다.

여튼! 이 문제는 House Robber 시리즈 2다. 이 전에 첫번째 House Robber 에서 선택 / 선택X 의 갈래를 두고 dp[i-2] + 현재 값 혹은 선택하지 않는 선에서 지금까지 최고 값인 dp[i-1]의 최고값으 구했었다. 그런데 이번 문제는 집이 원 모양으로 배치되어 있어서 첫번째 집과 마지막 집은 서로 옆에 있는것을 판단되어 집을 털수가 없다.

난 이 문제를 접근할때 그냥 단순히 i-2 가 첫번째 집이 아닌 이상 이 전과 똑같은 풀이겠다 하고 풀었는데 테스트 케이스에서 망했다. 생각을 좀 더 해보니 dp[1] 을 Max값으로 첫번째와 두번째 값으로 설정했는데 애초에 마지막 집은 첫번째 집을포함 못시키기에 말이 안됐다.

지금 적으면서도 헷갈릴 수 있지만 결론은 첫번째와 마지막집은 공존 할 수 없기에 분리를 해서 DP 테이블을 적용시켜줘야했다.

class Solution {

    public int find_dp(int[] nums, int start, int end){
        int[] dp = new int[nums.length]; 
        dp[start] = nums[start]; 
        dp[start+1] = Math.max(nums[start],nums[start+1]); 

        for(int i = start + 2; i < end; i++){
            dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]); 
        }

        return dp[end-1]; 
    }
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0]; 
        if(nums.length == 2) return Math.max(nums[0],nums[1]); 
        return Math.max(find_dp(nums,0,nums.length-1), find_dp(nums,1,nums.length)); 
    }
}

로직이 필요했던 문제였고 조금 어려웠던거 같다.