원형으로 배치되어 있는 집이므로 첫번째 집과 두번째 집을 선택하는 경우를 나누어 문제를 간략화 하자.

다음 그림과 같이 첫번째~세번째 집을 선택하는 경우는 정해져 있다.

이후 부터는 자기 자신이 선택할 수 있는 가장 최근 집 중에서 누적 합이 가장 큰 숫자를 그때그때 선택해주면 된다.

풀이 코드

class Solution {
    public int solution(int[] money) {
        int answer = 0;
        
        int[] start_0 = new int[money.length];
        int[] start_1 = new int[money.length];
        
        //초기화
        for(int i=0; i<money.length; i++) {
            start_0[i] = money[i];
            start_1[i] = money[i];
        }
        
        //못가는 집은 -1로 표시
        start_0[1] = -1;
        start_1[0] = -1;
        start_0[2] += start_0[0];
        
        //DP start
        for(int i=3; i<money.length; i++) {
            start_0[i] += Math.max(start_0[i-2], start_0[i-3]);
            start_1[i] += Math.max(start_1[i-2], start_1[i-3]);
        }
        
        int max_0 = Math.max(start_0[money.length-2], start_0[money.length-3]);
        int max_1 = Math.max(start_1[money.length-1], start_1[money.length-2]);
        
        answer = Math.max(max_0, max_1);
        
        return answer;
    }
}