[LeetCode] 198. 집 도둑(House Robber) [Java, DP]

문제

[문제 설명]

당신은 전문적인 도둑으로, 한 거리에 있는 집들을 털 계획을 세우고 있습니다. 
각 집에는 일정한 금액의 돈이 숨겨져 있습니다. 

그러나 인접한 집들은 보안 시스템이 연결되어 있어, 
같은 밤에 두 개의 인접한 집에 침입하면 자동으로 경찰에 신고됩니다.

정수 배열 nums가 주어지며, 이 배열은 각 집에 숨겨진 돈의 금액을 나타냅니다. 
경찰을 경고하지 않으면서 오늘 밤에 털 수 있는 최대 금액을 반환하세요.

[제한 사항]

1 <= nums.length <= 100 (중요)
0 <= nums[i] <= 400

[입출력 예시]

nums	return
[1, 2, 3, 1]	4
[2, 7, 9, 3, 1]	12

[입출력 예시 설명]

입출력 예#1
1번 집(nums[0])을 털고, 3번 집(nums[2])을 털면 됩니다.

입출력 예#2
1번 집, 3번 집, 5번 집을 털면 됩니다.

문제 분석

❗nums.length 가 2 이하인 것에 대한 예외 처리가 필요함.

[반례 테스트 케이스]

nums = [3] , answer = 3
nums = [3,5], answer = 5

인접한 곳은 방문하지 않는다. 즉, dp[n-2]와 dp[n-3]을 비교하여 최댓값이 그 다음 돈에 영향을 미치게 된다.

정답 코드

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, -1);

        if(nums.length <= 2) {
            if(nums.length == 1) return nums[0];
            else if(nums.length == 2) return Math.max(nums[0], nums[1]);
        } 
        
        // basecase
        dp[0] = nums[0];
        dp[1] = nums[1];
        dp[2] = nums[0]+nums[2];
        // logic
        for(int i=3; i<nums.length; i++) {
            dp[i] = Math.max(dp[i-2], dp[i-3]) + nums[i];
        }
        
        // 출력
        answer = Math.max(dp[nums.length-1], dp[nums.length-2]);
        return answer;
    }
}