프로그래머스 도둑질 - Java

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

프로그래머스

 

로직 

집이 원형으로 배치되어 있다는 것이 이 문제의 함정이다.

첫 번째 집에서 훔쳤는지 안 훔쳤는지 따라 마지막 집을 훔칠 수 있는 여부가 달라지기 때문이다. 

그래서 첫 번째 집 턴 경우 / 안 턴 경우 2가지 모두 DP돌리고, 그 두가지 중 max 값 찾는 것으로 로직을 짠다. 

 

점화식 DP[i] -> i번째 집까지 방문했을 때 얻을 수 있는 최대 금액 

1) 

첫 번째 집을 고른 경우에는 DP[0] = DP[1] = money[0]이다. 마지막 DP[last]는 DP[last-1]을 그대로 가지고 온다. 첫 번째 집을 들렸기 때문에 마지막 집은 들릴 수 없기 때문. 

2) 

첫 번째 집을 안 들른 경우에는 DP[0] = 0, DP[1] = money[1]이다. 마지막 DP[last]는 DP[last-2] + money[last]이다. last-1번째 집을 안털어야 마지막 집을 털 수 있기 때문이다. 

 

1과 2 두 가지 경우 모두 계산해서, 둘 중 최댓값이 정답이다. 

 

추가로, 집이 3채인 경우는 한 집만 털 수 있기 때문에 max값만 구해서 바로 리턴하면 된다. 근데 이 코드는 안 넣어도 효율성 검사 통과하는데에는 지장이 없었다. 

 

전체 코드 

class Solution {
    public int solution(int[] money) {
        int last = money.length-1;
        
        if (last == 2) {
            int max = Integer.MIN_VALUE;
            for (int i = 0; i <= last; i++) {
                max = Math.max(max, money[i]);
            }
            return max;
        }
        
        // 첫 번째 집 고른 경우
        int[] DP = new int[money.length];
        DP[0] = money[0];
        DP[1] = money[0];
        for (int i = 2; i <= last-1; i++) {
            DP[i] = Math.max(DP[i-2] + money[i], DP[i-1]);
        }
        DP[last] = DP[last-1];
        int answer = DP[last];
        
        // 첫 번째 집 안 고른 경우
        DP = new int[money.length];
        DP[0] = 0;
        DP[1] = money[1];
        
        for (int i = 2; i <= last-1; i++) {
            DP[i] = Math.max(DP[i-2] + money[i], DP[i-1]);
        }
        DP[last] = DP[last-2] + money[last];
        
        answer = Math.max(answer, DP[last]);
        return answer;
    }
}