LeetCode 198. House Robber

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

House Robber - LeetCode

 

Dynamic Programming 활용 문제

난이도 : medium

 

* IT's LIT 3주차

class Solution {

    /* Runtime: 0 ms, Memory: 40.1 MB */
    public int rob(int[] nums) {
        // 각 소문제별 해를 저장할 어레이
        int[] max = new int[nums.length];

        // 1채, 2채까지는 단순 계산
        if(nums.length == 1) {
            return nums[0];
        }
        max[0] = nums[0];
        max[1] = Math.max(max[0], nums[1]);
        if(nums.length == 2) {
            return max[1];
        }
        

        // 집이 3채인 경우부터 반복문 돌리기
        for(int i=2; i<nums.length; i++){
            max[i] = Math.max(nums[i]+max[i-2], max[i-1]);
        }

        return max[nums.length-1];
    }
}

 

소문제 나누는법

 

n번째 집을 터느냐 마느냐를 기준으로
 - n번째 집을 털거면 이웃한 집을 제외한 n-2부터 0까지의 집 중에서 최대값과 n번째 집의 값을 더하고 
 - n번째 집을 안털거면 이웃한 집을 털수 있으므로 n-1부터 0까지의 집 중에서 최대값을 비교해서
더 큰거 고르기

 

 

* 참고

NeetCode 영상

https://www.youtube.com/watch?v=73r3KWiEvyk