Programmers 도둑질 java 풀이

문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

 

나의 풀이

 DP문제 답게 훔치는 돈을 더해서 큰 값을 리턴하기로하고 문제풀이를 시작. 반복되는 패턴을 고민해보니 몇 가지 규칙이 보였는데,

 

 1. 첫번째 집을 털면 마지막 집은 털 수 없다. 집들이 원형으로 연결되기 때문에 첫번째 집과 이웃하게된다.

 2. 두번째 집을 털면 첫번째 집은 털 수 없다. 

 3. n번째 집 다음 n+1번째 집은 털수가 없기 때문에, n+2와 n+3 집중에서 큰돈을 가진 집을 선택해야한다.

 

이와 같은 규칙은 보였는데 문제는, n+3번째를 선택했을 경우 n+4가 큰값이면 어찌해야 하나 라는 문제였다. 순간 든 생각으로 n+3번째 집 선택을 포기하고 다시 n+2와 n+4를 선택해야하나 싶었는데, 뒤에서 뒤쪽에서 부터 바라보면 문제가 없었다. 다시 말해 n+2번을 기준으로 바라볼때 n번째 집과 n+2번째 집를 선택하는게 나을지, 아니면 n도 n+2도 포기하고 n+1을 선택하는게 나을지를 고민하면 되는 것. 

몇 가지의 DP 문제를 풀면서 보니 진행방향으로 생각하기보다 한차례 앞에서 뒤를 바라보는 식의 문제접근이 해답을 찾기 쉬운경우가 많은 것 같다.

 

코드

import java.util.*;

class Solution {
    public int solution(int[] money) {
        int[] arr0 = new int[money.length];
        int[] arr1 = new int[money.length];
        
        arr0[0] = arr0[1] = money[0];
        
        arr1[0] = 0;
        arr1[1] = money[1];
        
        for(int i=2; i<money.length-1; i++) {
            arr0[i] = Math.max(arr0[i-2]+money[i], arr0[i-1]);
            arr1[i] = Math.max(arr1[i-2]+money[i], arr1[i-1]);
        }
        
        
        int leng = money.length-1;
        arr1[leng] = Math.max(arr1[leng-2]+money[leng], arr1[leng-1]);
        
        return Math.max(arr0[leng-1], arr1[leng]);
    }
}