[Algo Rhythm🕺💃] 프로그래머스 고득점 kit 도둑질

📚 문제 설명

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

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

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

 

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.

• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

 

🎯 어떻게 풀었나

Backtracking을 이용한 첫번째 시도 (0/ 100) => 정확성은 모두 시간 초과, 효율성은 모두 통과 🙅‍♂️🙅‍♀️🙅

class Solution {
    private static int max = Integer.MIN_VALUE;
    private static int sum = 0;
    
    public int solution(int[] money) {
        int n = money.length;
        boolean[] visited = new boolean[n];
        
        backtrack(visited, money, 0, n / 2);
        
        return max;
    }
    
    public void backtrack(boolean[] visited, int[] money, int lev, int limit) {
        if(limit == lev) {
            max = Math.max(max, sum);
            return;
        }
        
        for(int i = 0; i < money.length; i++) {
            int left = (i == 0) ? money.length - 1 : i - 1;
            int right = (i == money.length - 1) ? 0 : i + 1;
            
            
            if(visited[i] == false) {
                visited[left] = true; 
                visited[right] = true;
                visited[i] = true;
                
                sum += money[i];
                backtrack(visited, money, lev + 1, limit);
            }
            
            visited[left] = false; 
            visited[right] = false;
            visited[i] = false;
            sum -= money[i];
        }
    }
}

 

DP를 이용한 최종 코드

class Solution {
    public int solution(int[] money) {
        int n = money.length;
        int[] arr = new int[n];
        int result1, result2;
        
        // result1 => (0 ~ n - 2)까지
        arr[0] = money[0];
        arr[1] = Math.max(money[0], money[1]);
        
        for(int i = 2; i < n - 1; i++) {
            arr[i] = Math.max(money[i] + arr[i - 2], arr[i - 1]);
        }
        
        result1 = arr[n - 2];
        
        // result2 => (1 ~ n - 1)까지
        arr[1] = money[1];
        arr[2] = Math.max(money[1], money[2]);
        
        for(int i = 3; i < n; i++) {
            arr[i] = Math.max(money[i] + arr[i - 2], arr[i - 1]);
        }
        
        result2 = arr[n - 1];
 
        return Math.max(result1, result2);
    }
}

 

🧐 왜 저렇게 풀었나

Backtracking을 이용한 첫번째 시도

모든 집은 가지고 있는 돈이 0 이상이다. 그래서 도둑은 일반적으로 많은 집을 털수록 더 많은 돈을 훔칠 수 있다. 그러나 도둑은 서로 인접한 집은 털 수 없다. 이런 상황에서 만약 마을에 n개의 집이 있다면 도둑은 최대한 많은 돈을 훔치기 위해 n / 2개의 집을 털어야 한다. 이를 시각화하면 다음과 같고 이는 backtracking을 이용해서 구현하기에 안성맞춤이다.

 

 

 

하지만 문제는 효율이었다. 모든 경우를 다 확인하기 때문에 정확하지만 느리다. 개선할 필요가 있었다.

 

DP를 이용한 최종 코드

마을에 집들이 동그랗게 배치되어 있는 것이 아니라 일렬로 배치되어 있다고 가정하자.

만약 도둑이 한 집씩 차례대로 방문하면서 털지 말지를 결정하는데 다음과 같이 두번째 집을 방문했다고 가정해보자. 이때 도둑이 두번째 집을 턴다면 첫번째 집은 털 수 없다. 반대로 도둑이 두번째 집을 털지 않는다면 첫번째 집을 털 수 있다.

 

 

이를 통해 우리는 도둑은 (두번째 집을 털었을 때 얻을 수 있는 금액 + 0번째 집을 털었을 때 얻을 수 있는 돈)이 (첫번째 집을 털었을 때 얻을 수 있는 금액)보다 클 때 두번째 집을 털어야 한다는 것을 알 수 있다.

 

이를 더 확장시키면 도둑이 n번째 집을 털어야 하는 기준은 (n번째 집을 털었을 때 얻을 수 있는 금액 + n - 2번째 집까지 확인해서 얻을 수 있는 최대의 금액)이 (n-1번째 집까지 확인해서 얻을 수 있는 최대의 금액)이라는 사실을 알 수 있다.

 

하지만 우리의 상황은 위와 조금 다르다. 마을은 일렬로 배치되어 있지 않고 동그랗게 배치되어 있다.

그래서 0번째 집을 털면 n-1번째 집을 털 수 없다. 반대로 0번째 집을 털지 않으면 n-1번째 집을 털 수 있다.

이를 시각화하면 다음과 같고 이를 통해 우리는 0번째 집부터 n-2번째 집까지 털었을 때 얻을 수 있는 최대의 금액과 1번째 집부터 n-1번째 집까지 털었을 때 얻을 수 있는 최대의 금액 중 더 큰 금액을 고르면 된다는 것을 알 수 있다.

 

 

📖  무엇을 배웠나