[프로그래머스 Level.4] 도둑질 (동적계획법) (Java)

문제 링크

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

프로그래머스

 

 

 

코딩테스트 연습 > 동적계획법(Dynamic Programming) > 도둑질

 

 

 

 

문제 설명

 

 

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

 

 

 

 

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

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

 

 

 

제한사항

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

 

 

입출력 예

 

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

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    public int solution(int[] money) {
        int answer = 0;
        
        int[] dp1 = new int[money.length];
        int[] dp2 = new int[money.length];
        
        // 처음꺼부터 마지막-1까지, 처음에는 0 넣어주기 (ex. 0, 1, 2, 3)
        dp1[1] = money[0];
        for(int i=2; i<money.length; i++)
            dp1[i] = Math.max(dp1[i-1], dp1[i-2] + money[i-1]);
        
        // 처음+1부터 마지막까지, 처음에는 0 넣어주기 (ex. 0, 2, 3, 1)
        dp2[1] = money[1];
        for(int i=2; i<dp2.length; i++)
            dp2[i] = Math.max(dp2[i-1], dp2[i-2] + money[i]);
        
        answer = Math.max(dp1[money.length-1], dp2[money.length-1]);
        
        return answer;
    }
}

 

풀이

1. 이 문제는 질문하기를 보고 dp를 이용하여 문제 푸는 방법을 참고하여 풀었다.
2. 모든 위치에서 최고의 값을 고르는 모든 경우의 수를 따져봐야 하는데 양 끝이 연결 되어있는 원형 탐색이므로 첫 번째 값을 포함할 때와 마지막 값을 포함할 때의 두 경우를 나누어 판단해야 한다.
   첫 번째 값을 선택하면 마지막 값을 선택 못하고 마지막 값을 선택하면 첫 번째 값을 선택하지 못하기 때문이다.
3. 이렇게 두 경우를 나누면 원형 탐색의 문제를 해결 할 수 있다.
4. 그리고 dp 배열을 생성하여 최대값을 채워나가는 점화식을 세우면 된다.
5. 문제는 인접하지 않은 집을 털면서 훔칠 수 있는 돈의 최대값을 찾는 것이다.
   바로 전의 집을 털었으면 이번 집을 털지 못하고 전전집을 털었으면 이번 집은 털 수 있다.
   따라서 전의 집을 털었을 때까지의 최대값과 전전집까지 털었을 때의 최대값 + 이번 집을 털은 경우 중에 최대값이 된다. 따라서 점화식을 세워보면 dp[i] = Math.max(dp[i-1], dp[i-2] + money[i]) 로 세울 수 있다.
6. 여기서 한 가지 더 고려해야 할 점이 있는데 점화식을 보면 i-2를 체크하게 되므로 i=2부터 시작해야 하는 것을 알 수 있다. 그러나 아까 원형탐색 때문에 경우를 나누었기 때문에 한 가지는 첫 번째 값부터 마지막 전까지 탐색하고 다른 한 가지는 두 번째 값부터 마지막까지 탐색한다고 했던 것을 알 수 있다.
   예를 들면 원형 배열 money가 [1, 2, 3, 1]이면 [1, 2, 3]과 [2, 3, 1]의 경우를 나누어서 해야 한다고 했다.
   이렇게 되면 후자의 경우에 money의 3번째 위치부터 계산하여 점화식을 적용시키게 해야하는데 이러면 첫 번째와 두 번째 위치를 비교하지 못하기 때문에 안된다. 그래서 분리된 배열에 각각 첫 번째 index에 0을 추가하여 똑같이 모든 경우를 고려하여 탐색 할 수 있게 해야 한다. ([1, 2, 3]과 [2, 3, 1] 에서 [0, 1, 2, 3]과 [0, 2, 3, 1]로 변경)
7. 이렇게 두 가지의 경우로 나누었으니 dp 배열 또한 각각의 경우를 체크하기 위해 2개 생성한다.
   처음은 0으로 채우면 되니 dp[0]은 그대로 두고 각각 dp[1]은 각각 money의 첫 번째 값과 두 번째 값으로 채워준다.
   그리고 위에서 세웠던 점화식대로 monye를 for문을 돌면서 탐색하여 dp 배열을 채운다.
   첫 번째 값부터 시작하는 경우에는 money 배열 맨 앞에 0이 있기 때문에 점화식이 dp[i] = Math.max(dp[i-1], dp[i-2] + money[i-1] 가 된다. 두 번째 값부터 시작하는 경우는 첫 번째 값이 0으로 바뀌었다고 생각하면 되므로 처음에 세웠던 점화식 그대로 적용하면 된다.
8. 이렇게 각각의 dp 배열을 채운 후에 최종적으로 두 dp의 마지막 값을 비교하여 더 큰 값이 최종적으로 최대값이 된다.