[프로그래머스][코딩테스트 고득점 Kit][java] 도둑질

https://school.programmers.co.kr/learn/courses/30/lessons/42897

프로그래머스

전체 코드

class Solution {
    public int solution(int[] money) {
        // 첫 번째 집부터 시작
        int[] DP1 = new int[money.length]; 
        DP1[0] = money[0];
        DP1[1] = money[0];
        
        // 첫 번째 집을 넘기고 두 번째 집부터 시작
        int[] DP2 = new int[money.length]; 
        DP2[1] = money[1];
        
        for(int i=2; i<money.length; i++){
        // dp[i] = max(i-1번 째 집까지의 최댓값, i-2번 째 집까지의 최댓값+현재 집)
            DP1[i] = Math.max(DP1[i-1], DP1[i-2]+money[i]);
            DP2[i] = Math.max(DP2[i-1], DP2[i-2]+money[i]);
        }
        
        // 첫 번째 집부터 시작한 경우 마지막 집 도둑질이 불가하고
        // 두 번째 집부터 시작한 경우 마지막 집 도둑질이 가능하므로
        // 위 두 가지 경우 중 최댓값을 return
        return Math.max(DP1[money.length-2],DP2[money.length-1]);
    }
}