[프로그래머스/Java] 도둑질(DP 문제) 풀이

프로그래머스 알고리즘 고득점 Kit의 동적계획법(DP) 파트 문제인 '도둑질'을 자바로 풀어보았다.

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

프로그래머스

 

 

 사실, 문제 자체의 알고리즘이나 접근법은 어렵지 않다. 그냥 차례로 money 배열을 순회하며, i번째 element보다 인덱스가 최소 2개 앞서있는 dp 배열 요소(인덱스가 i-1보다 작은 요소) 중 최댓값에 현재값을 더하여 dp[i]에 저장해 나가면 된다. 그리고 마지막으로 dp 배열에 저장된 값 중 최댓값을 리턴하면 된다.

 다만 이렇게 했을 때 오류를 발생시키는 점은 "첫번째 요소와 마지막 요소 역시 연결되어 있다"는 점이다. 문제에서 집들이 동그랗게 배치되어 있다고 했기 때문에 첫 번째 요소와 마지막 요소도 인접한 집이다. 따라서 두 집을 함께 훔칠 수 없다. 하지만 마지막 요소를 탐색하는 경우에 다다르면 첫 번째 요소가 포함되었는지 아닌지 알 수 없다. 

 그래서 내가 이를 해결하기 위해 선택한 방법은 dp 배열을 두 개 만들어 하나는 money 배열을 앞에서부터 탐색하며 만들고, 하나는 뒤에서부터 탐색하며 만드는 것이다. 이 때, 앞에서부터 탐색하며 만드는 배열에서 최댓값을 가져올 때는 마지막 요소 전까지 고려된 즉, dp[len-2]의 값까지를 고려했을 때 최댓값이어야 한다. 뒤에서부터 탐색하며 만드는 배열의 경우 반대로 dp[1]까지만 고려해야 한다. 그리고 둘의 최댓값을 비교하여 더 큰 쪽이 이 문제에 답이 된다. 

import java.util.*;

class Solution {
    public int solution(int[] money) {
        int len = money.length-1;
        int[] asc = new int[len+1];
        int[] des = new int[len+1];
        int a_max = money[0], d_max = money[len];
        for (int i = 0; i <= len; i++) {
            if (i < 2) {
                asc[i] = money[i];
                des[len-i] = money[len-i];
                continue;
            }
            
            asc[i] = a_max + money[i];
            des[len-i] = d_max + money[len-i];
            
            a_max = Math.max(a_max, asc[i-1]);
            d_max = Math.max(d_max, des[len-i+1]);
        }
        
        return Math.max(a_max, d_max);
    }
}

 

 

 하지만 이렇게 했을 때 코드가 너무 복잡한 것 같아서 다른 분들의 코드를 참고했더니, 코드를 획기적으로 줄인 방법들이 있었다. 그 중 가장 간결한 방식은, 처음에 배열 두 개를 만들되, 하나는 첫 번째 요소를 포함하고 두 번째 요소를 빼고 만들고, 나머지 하나는 첫 번째 요소를 빼고 두 번째 요소를 포함하여 만드는 방식이었다. 그 코드를 참고하여 다시 코드를 작성해 보았다.

 우선 위에 내가 처음에 작성한 코드에서 dp 배열의 i-2 값에 바로 i번째 money 값을 더하지 못한 이유가 개수가 3개인 경우 적용이 되지 않아서였다. 예를 들어, [10, 1, 10]의 배열이 있으면, 첫 번째 값이나 마지막 값을 출력할 수 없기 때문에 결과가 1이 나왔다. 하지만 아래 코드를 활용하는 경우 마지막 요소까지 고려할 수 있기 때문에 더 간단하게 dp[i-2]를 사용해 줄 수 있었다.

class Solution {
    public int solution(int[] money) {
        int len = money.length;
        int[] fir = new int[len];
        int[] sec = new int[len];
        
        fir[0] = money[0];  fir[1] = money[0];
        sec[0] = 0; sec[1] = money[1];
        for (int i = 2; i < len; i++) {
            fir[i] = Math.max(fir[i-2]+money[i], fir[i-1]);
            sec[i] = Math.max(sec[i-2]+money[i], sec[i-1]);
        }
        
        return Math.max(fir[len-2], sec[len-1]);
    }
}