[프로그래머스] 도둑질

programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

문제 설명

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

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

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

제한사항

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

풀이

일단, 모든 집들이 원형으로 배치되어 있다는 것에 주목해야 한다.

 

일반적인 DP 문제처럼 "dp[n] = n 번째 집까지 털었을 때 최대로 털 수 있는 돈" 으로 정의하고 풀면,

 

첫번째 집과 마지막 집을 동시에 털어버리는 경우까지 포함되어 정확한 해답을 낼 수가 없다.

 

따라서, 

1. 첫번째 집을 고르는 경우(마지막 집은 털지 않는다)

2. 마지막 집을 고르는 경우(첫번째 집은 털지 않는다)

 

이렇게 둘로 나누어, 둘 중 최댓값을 return 하는 형태로 문제를 풀었다.

 

import java.util.*;

class Solution {
    public int solution(int[] money) {
        int answer = 0;
        
        
        int money2[] = new int[money.length];
    
        int dp[] = new int[money.length]; 
        int dp2[] = new int[money.length];
        
        for(int i=0; i<money.length; i++){
            money2[i] = money[i];
        }

        if(money.length == 3){
            answer = Math.max(Math.max(money[0], money[1]), money[2]);
        }else{
            
                    
            money[0] = 0;
            money2[money.length-1] = 0;
        
            // 첫번째 집을 고르는 경우
            dp2[0] = money2[0];
            dp2[1] = Math.max(money2[0], money2[1]);
            
            // 마지막 집을 고르는 경우
            dp[0] = money[0];
            dp[1] = money[1];
            
            for(int i=2; i<dp.length; i++){
                dp[i] = Math.max(dp[i-2] + money[i], dp[i-1]);
                dp2[i] = Math.max(dp2[i-2] + money2[i], dp2[i-1]);
            }

            answer = Math.max(dp[money.length -1], dp2[money.length -1]);

        }
        
        return answer;
    }
}

 

처음에 위 알고리즘대로 코드를 짤 때는, 뭔가 풀이가 더 복잡할 것 같다는 생각에..

확신을 가지지 못하고 코드를 짰더니 40점이 나와서, 다른 풀이를 생각해보느라 시간이 더 오래 걸렸다.

 

일단 코드를 짤 때는 생각해낸 알고리즘에 확신을 가지고, 코드 짜는데만 집중하는 게 필요할 것 같다..