[프로그래머스] 도둑질-JAVA

문제 링크

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

코딩테스트 연습 - 도둑질

 

이 문제는 동적계획법으로 풀이하였다.

 

풀이 방법

 

이 문제의 분기점은 처음 도둑질을 할 때, 첫 번째 집을 고르냐, 두 번째 집을 고르냐에 따라 크게 두가지로 나뉜다.

인접한 집은 털 수 없다는 제한으로 두 경우로 나뉘어 집을 터는 루트가 정해지기 때문이다.

 

필자의 풀이 방법을 그림을 통해 자세히 보도록 하자.

 

 

 

 

 

 

왼쪽에 보이는대로, 처음 세 개의 집은 터는 방식이 정해져있다.

 

세 번째 집 입장에서는 털 수 있는 집이 첫 번째 집밖에 없다.

 

따라서 세 번째 집의 경우, 자신의 금액 10원과 첫 번째 집을 턴 50원을 합쳐 60원이 들어있게 된다.

 

 

 

 

 

 

 

 

 

 

 

4번째 집 부터는 n-2번째 집과 n-3번째 집의 금액을 비교한다. n-2번째 금액이 더 크기 때문에 해당 집을 털어 70원을 벌고 현재 위치의 집을 털어 총 90원을 벌게 된다.

 

 

즉, 4번째 집에는

2번째 집 + 4번째 집을 턴 금액이 들어있다.

 

 

 

 

 

 

 

 

 

 

5번째 집도 마찬가지이다.

3번째 집과 2번째 집을 비교해본다.

 

3번째 집 : 1번째 집 털고 3번째 집 털었음

2번째 집 : 2번째 집만 털었음

 

이때 2번째 집에서 턴 금액이 더 크다.

 

따라서 5번째 집에는

2번째 집 턴 금액 + 5번째 집 턴 금액이 합산하여 들어가있다.

 

 

 

 

 

 

 

 

마지막 집도 같은 방식으로 판별한다.

 

3번쨰 집 : 1번째 집 + 3번째 집

4번째 집 : 2번째 집 + 4번째 집

 

 

둘 중 2번 + 4번집을 턴 금액이 더 크다.

 

따라서 마지막 집은

2번 + 4번 + 6번을 턴 금액이 들어있다.

 

 

 

 

 

 

 

결과를 정리하면 이렇게 된다.

 

 

 

 

 

 

 

 

맨 마지막 두 집을 비교하여, 더 많은 금액을 턴 집을 return한다.

 

 

 

 

 

 

 

 

 

 

 

 

 코드 풀이

 

// 0번째부터 시작, 1번째부터 시작
// dp_first[n]의 값은 dp_first[n - 2] dp_first[n - 3]중에 큰 값
// dp_second[n]도 마찬가지. 단, 둘의 차이는 시작한 집.
class Solution {
    public int solution(int[] money) {
        int[] dp_first = new int[money.length];
        int[] dp_second = new int[money.length];
        
        for(int i = 0; i < money.length; i++) {
            dp_first[i] = money[i];
            dp_second[i] = money[i];
        }
        dp_first[1] = -1;
        dp_second[0] = -1;
        dp_first[2] += dp_first[0];
        for (int i = 3; i < money.length; i++) {
            dp_first[i] += Math.max(dp_first[i - 2], dp_first[i - 3]);
            dp_second[i] += Math.max(dp_second[i - 2], dp_second[i - 3]);
        }
        int first_max = Math.max(dp_first[money.length - 2], dp_first[money.length - 3]);
        int second_max = Math.max(dp_second[money.length - 1], dp_second[money.length - 2]);
        return Math.max(first_max, second_max);
    }
}

최소 집의 개수는 3개이다.

따라서 필자는 3번째 집까지의 경우를 미리 구해두고, 3개 이상일 경우부터는 for문을 돌려 찾아보도록 하였다.