프로그래머스_도둑질(JAVA)

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

코딩테스트 연습 - 도둑질

[문제 설명]

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

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

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

제한사항

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

입출력 예

money	return
[1, 2, 3, 1]	4

---

[문제 분석]

해당 문제는 dynamic programming 문제로 해결하면 되는데, 도둑이 집을 터는 경우의 수는 두가지로 나눌 수 있다.

첫 번째는 0번째 집을 터는 것이고, 두 번째는 0번째 집을 털지 않는 것이다. 즉 마지막 집을 터는 것이라고 봐도 된다. 처음 문제를 풀 때 집이 동그랗게 배치되어 있음을 고려한 경우의 수인 것이다.

dp 배열은 0번째 집을 터는 경우고,

dp2 배열은 0번째 집을 털지 않는 경우를 다룬 배열이다.

 

따라서 dp는 0번째 집을 터는 경우이므로 dp[0]은 money[0], 0번째 집을 턴 경우 1번째 집은 털 수 없으므로 dp[1]의 값도 변화없이 money[0]의 값을 대입한다.

dp2는 0번째 집을 털지 않은 것이므로 dp2[0]에는 0을, 0번째 집을 털지 않았으므로 1번째 집을 털 수 있다. 따라서 dp2[1]에는 money[1]의 값을 넣어준다.

 

dp[i]의 값은 dp[i-2]+money[i]와 dp[i-1] 중 더 큰 값을 넣어주면 된다.

 

[코드]

class Solution {
   
    public int solution(int[] money) {
        int answer = 0;
        int[] dp =new int[money.length-1];
        int[] dp2= new int[money.length];
        
        dp[0]=money[0];
        dp[1]=money[0];
        
        dp2[0]=0;
        dp2[1]=money[1];
        
        //0번째 집을 터는 경우
        for(int i=2;i<money.length-1;i++){
            dp[i]=Math.max(dp[i-2]+money[i],dp[i-1]);
        }
        
        //0번째 집을 털지 않는 경우, 즉, 마지막 집을 터는 경우
        for(int i=2;i<money.length;i++){
            dp2[i]=Math.max(dp2[i-2]+money[i],dp2[i-1]);
        }
         
        return Math.max(dp[money.length-2],dp2[money.length-1]);
    
    }
}