프로그래머스 DP - 도둑질

동적계획법 도둑질 문제

 

동적계획법 : 불필요한 계산을 줄이고 최적해를 찾는 방법

 

 

코드

class Solution {
    public int solution(int[] money) {
        int answer = 0;
        int dp[] = new int[money.length];
        int dp2[] = new int[money.length];

        dp[0] = money[0];
        dp[1] = money[0];

        dp2[0] = 0;
        dp2[1] = money[1];
        for (int i = 2; i <= money.length-2; i++) {

            dp[i] = Math.max(dp[i-2] + money[i],dp[i-1]);
            dp2[i] = Math.max(dp2[i-2] + money[i],dp2[i-1]);
        }
        dp2[money.length-1] = Math.max(dp2[money.length-3] + money[money.length-1],dp2[money.length-2]);
        answer = Math.max(dp[money.length-2],dp2[money.length-1]);
        return answer;
    }
}

코드 내용 요약

dp[] = 첫번째 집을 무조건 도둑질 한다는 가정하의 최적해

dp2[] = 두번째 집을 무조건 도둑질 한다는 가정하의 최적해

 

dp, dp2로 나눈 이유 : 인접한 집을 도둑질하면 경보가 울리기 때문에 연속으로 있는 집을 도둑질 할 수 없어 시작점 집을 2개로 나눔

 

dp[0] = money[0];
dp[1] = money[0];

dp[0]과 dp[1]을 money[0]으로 넣은 이유는 dp는 첫번째 집을 도둑질 했을 때의 가정이고 dp[0] (첫번째 집을 도둑질 했을 때 최적해 => 첫번째 집의 돈) dp[1] (첫번째 집을 도둑질 했기 때문에 2번째 집을 도둑질 할 수 없어서 여전히 첫번째 집의 돈이 최적해)

 

dp[i] = Math.max(dp[i-2] + money[i], dp[i-1]);

dp2[i] = Math.max(dp2[i-2] + money[i], dp2[i-1]);

dp[i] = i번째 집에 도달했을 때 최적해

i번째 집 기준으로 두칸 전 (인접한 집은 도둑질 할 수 없기 때문에) 최적해와 i번째 집의 돈의 합과 i-1번째 최적해와 비교해서 더 큰 값을 dp[i]에 넣어줍니다. 그 이유는 i번째 집을 도둑질 했을 때 보다 i-1 집의 최적해가 더 클 경우 i번째 집을 도둑질 할 필요가 없어지기 때문에 위와 같은 크기 비교를 통해 최적해를 누적해 나감.

 

for문이 종료되고 dp2계산이 하나 더 추가 되는 이유는 dp는 첫번째 집을 도둑질 했기 때문에 마지막 집은 도둑질 하지 않아도 되기 때문에 i-2까지 for문이 동작했고 dp2는 두번째 집부터 시작했기 때문에 i-1까지 확인을 해야되기 때문 그래서 마지막 i-1 일 때의 계산을 추가로 함.