문제 출처

프로그래머스 코딩테스트 연습 > 동적 계획법 > 도둑질
https://school.programmers.co.kr/learn/courses/30/lessons/42897

문제 설명

도둑이 집을 털 때, 서로 인접한 집을 털면 경보가 울린다.
각 집마다 돈의 액수가 담긴 배열 money가 주어질 때, 도둑이 경보를 울리지 않고 훔칠 수 있는 돈의 최댓값을 return 하라.

접근 방법

첫 번째 집을 반드시 터는 경우와 첫 번째 집을 털지 않는 경우의 배열을 생성하여 접근한다.
첫 번째 집이 들어간 firstHouse 배열은 위치에서 전 집과 전전 집 + 현재 집 돈의 합을 비교하여 더 큰 값을 삽입한다.
단, 마지막 집이 들어가지 않으므로 반복문의 조건문으로 i<n-1을 설정한다.

첫 번째 집을 반드시 털지 않는 경우는 lastHouse 배열에서 첫 번째 집의 값을 0으로 설정하고, 현재위치에서 전 집과 전전 집 + 현재 집 돈의 합을 비교하여 더 큰 값을 삽입한다.

이 후, 두 배열의 각각 마지막 값인 firstHouse[n-2], lastHouse[n-1] 의 값을 비교하여 더 큰 값을 return 한다.

class Solution {
    public int solution(int[] money) {
        int n = money.length;
        if (n == 3){
            return Math.max(money[0], Math.max(money[1],money[2]));
            
        }
        
        int[] firstHouse = new int[n];
        firstHouse[0] = money[0];
        firstHouse[1] = money[0];
        for (int i = 2; i<n-1; i++){
            firstHouse[i] = Math.max(firstHouse[i-1], firstHouse[i-2] + money[i]);
        }
        
        int[] lastHouse = new int[n];
        lastHouse[0] = 0;
        lastHouse[1] = money[1];
        for(int i = 2; i<n; i++){
            lastHouse[i] = Math.max(lastHouse[i-1], lastHouse[i-2] + money[i]);
        }
        
        return Math.max(firstHouse[n - 2], lastHouse[n-1]);
    }
}

Review

class Solution {
    public int solution(int[] money) {
        int answer = 0;
        int N = money.length;
        
        // 첫 번째 집을 반드시 터는 경우
        int[] firstHouse = new int[N];
        firstHouse[0] = money[0];
        firstHouse[1] = money[0];
        
        for(int i = 2; i<N-1; i++){
            firstHouse[i] = Math.max(money[i]+firstHouse[i-2], firstHouse[i-1]);
        }
        // 첫 번째 집을 안 터는 경우
        int[] lastHouse = new int[N];
        lastHouse[0] = 0;
        lastHouse[1] = money[1];
        
        for(int i = 2; i<N; i++){
            lastHouse[i] = Math.max(money[i]+lastHouse[i-2], lastHouse[i-1]);
        }
        
        
        return Math.max(firstHouse[N-2],lastHouse[N-1]);
    }
}

알게된 점

처음 문제를 접했을 땐, 문제가 생소하여 첫 번째 집을 털면, 마지막 집을 못 턴다는 점에서 헤맸다. 추가로 가장 큰 값이 되야하므로 해당 위치에서 양 옆의 값을 비교하여 가장 큰 값들을 뽑아야하나 생각했지만, 생각보다 간단하게 순차적으로 값을 더해가면서 비교하면 되는 문제였다.

문제푼 흔적

Review