[JAVA] 도둑질 (코딩테스트 고득점 Kit [ 동적계획법(DP)]) - LEVEL3

📂문제 설명

 

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

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

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

 

제한사항

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

입출력 예

money                 return

[1, 2, 3, 1]

4

 

---

📂아이디어 및 알고리즘(문제 풀이)

• DP문제로 해결 할 수 있는 문제이며 집을 털때 한칸 씩 혹은 두칸 씩 넘으면서 값을 저장해 나가여 최댓값을 만들어 주면 되는 문제이다.
• 여기서 중요한점은 첫 번째 집과 마지막 집이 인접해 있기 때문에 첫 번째 집을 털면 마지막 집은 털지 말아야 한다. 반대로 마지막 집을 털면 첫번째 집은 털지 말아야 하는것이다. 
• 그래서 이를 구분하기 위해 DP1,2로 나누어 첫번째 집을 포함했을 경우와 포함하지 않았을 경우를 비교하여 최종적으로 더 큰 값을 가진 쪽을 출력하면 된다.
• 집은 최소 3채 부터 있기 때문에 초기 DP[0~1] 에는 초기값을 설정해 주어야한다. 
  • DP1[0] = 첫번째 집 돈,  DP1[0] = 두번째 집은 털지 말아야하기 때문에 DP1[0]과 같은 값을 준다.
  • DP2[0] = 첫번째 집을 털지 말아야하기 때문에 0, DP2[1] = 두번째 집 돈 을 넣어준다.
• for문에서는 집 수만큼 순회하면서 DP1 , DP2값들을 더해나간다.
  • DP1[i]에는 DP1[i-2]+ 현재 집 돈 과 DP1[i-1] 를 비교해 더 큰값을 넣어준다.
  • 마찬가지로 DP2도 구해준다. 
• DP1의 최댓값은 마지막 집을 제외해야 하므로 DP1[len-2], DP2의 최댓값은 마지막 집을 포함한 DP2[len-1]이다. 둘 중 큰 값을 return 하면 된다.

📂소스 코드

class Solution {
	   public int solution(int[] money) {
	        int len = money.length;
	        int[] DP1 = new int[len]; //첫번째부터 포함 
	        int[] DP2 = new int[len]; //두번째부터 포함 
	        
	        DP1[0] = money[0];
	        DP1[1] = money[0];

	        DP2[0] = 0;
	        DP2[1] = money[1];
            
	        for(int i=2;i<len;i++) {
	        	
	        	DP1[i] = Math.max(DP1[i-2] + money[i], DP1[i-1]);
	        	DP2[i] = Math.max(DP2[i-2] + money[i], DP2[i-1]);
	        		
	        }        
	        return Math.max(DP1[len-2], DP2[len-1]);       	        
	    }
}

 

📂후 기

처음 해결할 때는 DP배열을 하나만 사용하고 첫 번째 집과 마지막 집에 구분을 해주느라 코드가 길어지게 되어 해결했지만 정말 복잡한 코드가 되었다. hint로 DP두개를 사용하면 된다 해서 했더니 너무 편하게 구할 수 있었다고 한다. 🛴