도둑질 [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

 

풀이

우선은 집이 일자라고 생각하고 각각의 집을 a, b, c, d, e, f라고 하자.

a부터 시작할 때, a와 b는 선택권이 없이 a, b이다. c가 할 수 있는 선택 역시 a+c 뿐이다.

d의 경우 a+d, b+d가 가능하다.

e의 경우 b+e, c+e가 가능하다. a는 어차피 c에 포함될테니 생각할 필요가 없다.

f의 경우 c+f, d+f가 가능하다. a, b는 생각할 필요가 없다.

만약 a > b라면, d에 a+d가 들어가 있을 것이다.

이처럼 비교를 함에 있어서 결국은 자기 자신 -2, 자기 자신 -3만 비교해서 더 큰 쪽만 알아내면 된다.

그리고 최종적으로는 끝의 두 개를 비교하면 된다.

구현 과정에 있어서 사실 막상 필요한 것은 정수 4개지만, 메모리에 여유가 있어서 그냥 전체 배열을 만들어 각각에 저장하는 방식으로 구현하였다.

그렇다면 이제 순환을 생각해보자.

마지막 원소를 추가할 때, 과연 첫 번째 집이 내 계산 안에 포함되어있는가를 따지는 것은 너무 복잡하다.

이때 인접한 집은 도둑질 할 수 없으므로, 0번째 집과 n번째 집은 양립할 수 없다.

그렇다면 그냥 0~n-1까지와 1~n까지의 최대를 구한 다음 둘을 비교해주기만 하면 된다.

각각의 시간복잡도가 $O(N)$이기 때문에 2번 수행해도 큰 부담이 없다.

 

코드

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

        //3이면 그냥 세개 비교
        if(length < 4) {
            for(int i=0; i<length; i++) {
                answer = Math.max(money[i], answer);
            }
            return answer;
        }

        //4 이상에서
        int[] cacheA = new int[length];
        int[] cacheB = new int[length];

        // 0 ~ n-1 까지
        cacheA[0] = money[0];
        cacheA[1] = money[1];
        cacheA[2] = cacheA[0]+ money[2];

        for(int i=3; i<length-1; i++){
            cacheA[i] = Math.max(cacheA[i-3] + money[i], cacheA[i-2] + money[i]);
        }
        answer = Math.max(cacheA[length-2], cacheA[length-3]);

        // 1 ~ n 까지
        cacheB[1] = money[1];
        cacheB[2] = money[2];
        cacheB[3] = cacheB[1]+ money[3];

        for(int i=4; i<length; i++){
            cacheB[i] = Math.max(cacheB[i-3] + money[i], cacheB[i-2] + money[i]);
        }
        answer = Math.max(cacheB[length-1], answer);
        return answer;
    }
}

 

결과