알고리즘) 프로그래머스 DP, 도둑질

프로그래머스 고득점 Kit - DP

도둑질

 

문제 설명

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

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

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

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.

• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력 예

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

 

풀이

이전 게시글에서 언급했듯 DP 문제는 점화식과 메모이제이션이 핵심이다. 이 문제는 인접한 두 집을 털 수 없다는 조건 하나만 있어서, 비교적 수월한(?) 문제다. 2차원 배열로 선언해도 괜찮지만, 조금 더 가시적으로 확인하기위해 1차원 배열을 두 개 선언했던것 같다.

시작을 첫번째 집을 턴 경우와 두번째 집을 턴 경우, 두 변수를 이용해서 현재 위치한 집을 터는 것 + 전 전집 턴 돈과, 전 집까지 턴 돈을 비교하여 갱신해준다. 이 때, 유의할 점은 첫번째 집을 턴 경우로 시작하는 변수의 두번째 인덱스는 첫번째 집에서 턴 돈으로 초기화해야 한다는 것이다. 또한, 문제의 조건에 의해 첫번째 집을 턴 경우는 마지막 집을 털 수 없으므로, 해당 변수는 마지막 이전 인덱스를 리턴해줘야한다.

 

코드

package programmers;

public class KitDPThievery {
    private static int solution(int[] money) {
        //이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
        int len = money.length;
        int[] dp1 = new int[len], dp2 = new int[len];

        dp1[0] = money[0];  // 첫번째 돈 포함
        dp1[1] = money[0];  // 두번째 돈은 포함을 안할거니까 첫번째 애 입력
        dp2[1] = money[1];  // 두번째 돈 포함

        for (int i = 2; i <len; i++) {
            dp1[i] = Math.max(dp1[i-2]+money[i], dp1[i-1]);
            dp2[i] = Math.max(dp2[i-2]+money[i], dp2[i-1]);
        }

        return Math.max(dp1[len-2], dp2[len-1]);    // dp1에는 첫번째 집이 포함됐으니까 최대 길이 하나 전 IDX를 return
    }

    public static void main(String[] args) {
        int[] money = {1, 2, 3, 1};

        System.out.println(solution(money));
    }
}