DP - 도둑질

프로그래머스 (DP) - 도둑질

해당 문제는 원형의 집 배치라는 것을 생각하고, 첫번째 집을 선택하고, 마지막집을 선택하지 않은 경우, 첫번째 집을 선택하지 않은 경우로 나누어, dp[n] = Max(dp[n-2] + money[n], dp[n-1]) 이라는 기준으로 계산(2번째 전집을 털고, 현재 집을 털 경우와 이 전집을 턴경우) 식을 바탕으로 2가지 경우를 구한 후 두가지중 큰 값을 선택하여 값을 구했습니다.

public int solution(int[] money) {
        int homeLength = money.length;

        int[] dpFirstChoice = new int[homeLength];
        int[] dpFirstNotChoice = new int[homeLength];

        dpFirstChoice[0] = money[0];
        dpFirstChoice[1] = Math.max(money[0], money[1]);

        dpFirstNotChoice[1] = money[1];

        for (int i = 2; i < homeLength; i++ ) {
            dpFirstNotChoice[i] = Math.max(dpFirstNotChoice[i-1], dpFirstNotChoice[i - 2] + money[i]);
            if (i == homeLength -1) {
                dpFirstChoice[i] = dpFirstChoice[i - 1];
                break;
            } else {
                dpFirstChoice[i] = Math.max(dpFirstChoice[i-1], dpFirstChoice[i - 2] + money[i]);
            }
        }

        return Math.max(dpFirstNotChoice[homeLength - 1], dpFirstChoice[homeLength - 1]);
    }