[pro] 프로그래머스 level4 42897 도둑질 (Java) - dp

[문제]

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

프로그래머스

 

[풀이]

스티커 모으기2 문제와 똑같다!

 

1. 집이 원형으로 배열되어있으므로 첫번째 집을 터는 경우(마지막 집을 털 수 없음)와 안터는 경우로 나눈다.

2. dp[i]는 도둑이 i번째 집까지 왔을 때 훔칠 수 있는 돈의 최대값. 따라서 i번째 집을 터는 경우와 털지 않는 경우로 나눌 수 있다. 터는 경우 이전 집에 경보가 울리므로 dp[i-2] + money[i]가 될 것이고, 털지 않는 경우 dp[i-1]이 된다. 따라서 점화식은 dp[i] = Math.max(dp[i-2]+sticker[i], dp[i-1])

 

 

[코드]

 

class Solution {
    public int solution(int[] money) {
        int answer = 0;
        // money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return
        
        //dp[i] = 도둑이 i번째 집에 왔을 때 훔칠 수 있는 돈의 최댓값
        int[] dp = new int[money.length];
        
        //첫번째 집을 터는 경우
        dp[0] = dp[1] = money[0];
        for(int i=2; i<money.length-1; i++){
            //i번째 집을 터는 경우, 안터는 경우
             dp[i] = Math.max(dp[i-2]+money[i], dp[i-1]);
        }
        answer = dp[money.length-2];
        
        //첫번째 집을 안터는 경우
        dp[0] = 0;
        dp[1] = money[1];
        for(int i=2; i<money.length; i++){
            dp[i] = Math.max(dp[i-2]+money[i], dp[i-1]);
        }
        
        answer = Math.max(answer, dp[money.length-1]);
        
        return answer;
    }
}