[자바] 프로그래머스 - 도둑질 (코딩테스트 연습 Lv4)

문제 : Programmers-도둑질

 

 

  레벨 4라 보기엔 프로그래머스의 다른 레벨4 문제에 비해 너무 쉽다. DP가 개인적으로 내 최대 약점이라 생각하는데도 금방 점화식이 생각날 정도니 2~3정도가 적당할 것 같다. 레벨4 스킬 체크 딸 때 이거 나왔으면 더 꿀이었을 것 같다.

 

  일단 점화식은 간단하다. dp[i]를 i번 집을 털 때 얻을 수 있는 최대 돈이라 하면 아래와 같이 세울 수 있다.

  즉, 현재 i번 집을 털 때 얻을 수 있는 최대 돈은, 이전집을 털고 현재집을 털지 않는것과 이전으로 2번째 집을 털고 이번 집도 터는 것 중 max값을 선택하면 된다. 이렇게 하면 '100 1 1 100' 처럼 중간에 두 집을 건너띄고 털어야 하는 것 까지 한번에 해결된다(세 집을 건너띄는 경우는 없다. 그 경우라면 당연히 그 사이의 집은 터는게 무조건 이득이다.)

 

  아무튼 4레벨이 된 이유로 원형이라는 것 때문일 것 같은데, 그냥 dp를 둘로 나누어서 맨 첫번째 집을 턴 경우와 안턴 경우를 강제해서 진행하면 된다. 이 경우 맨 처음 집을 턴 경우엔 마지막집을 털면 안되므로 dp[마지막집-1]이 최대치이고, 처음 집을 털지 않은 경우 dp[마지막집]이 최대치 일 것 이다. 그러니 둘 중 최대치를 출력해주면 된다.

 

 

코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    public int solution(int[] money) {
        int len = money.length;
        int[] dpInclude0 = new int[len];
        int[] dpExclude0 = new int[len];
        dpInclude0[0] = dpInclude0[1] = money[0];
        dpExclude0[1] = money[1];

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

        return Math.max(dpInclude0[len-2], dpExclude0[len-1]);
    }
}