[Programmers:DP] 도둑질

❓문제

이웃한 집은 털 수 없다는 조건에서 도둑질했을 때 가장 많은 돈을 털 수 있는 방법

Return Max(도둑질 값)

---

🖐️손코딩

## 처음에 생각했던 방법
현재 위치 i에서 털 수 있는 집 중 가장 많은 돈을 보유한 집(leetcode 점프 게임과 유사한 방식)
-> Greedy 법으로 최적해를 보장하지 못함

dp[i] -> 0~i번째 집까지 고려했을 때 가능한 모든 경우의 돈의 합 중 최댓값

def rob()
	for(i:0~n)
		i를 터는 경우 : MAX(money[i], dp[i-2]+money[i])// dp[i-2]+Money[i] >= money[i] -> dp[i-2]+money[i]
    	i를 안터는 경우 : dp[i-1]
    	dp[i] = Max(dp[i-2]+money[i], dp[i-1])
    
def main()
	int a = rob() // 첫번째 집을 터는 경우
    int b = rob() // 첫번째 집을 털지 않는 경우
    
    return Max(a, b)

---

👩‍💻구현 코드

import java.util.*;

class Solution {
    private int rob(int[] money, int[] dp, int start, int end){
        dp[start] = money[start];
        dp[start+1] = Math.max(money[start], money[start+1]);
                               
        for(int i = start+2; i<=end; i++){
            if(i<2){
                dp[i] = money[i];
            } else {
                int a = money[i]+dp[i-2];
                int b = dp[i-1];
                dp[i] = Math.max(a, b);
            }
        }
        
        return dp[end];
    }
    
    public int solution(int[] money) {
        int answer = 0;
        int[] dp = new int[money.length];
        
        int a = rob(money, dp, 0, money.length-2);
        
        dp = new int[money.length];
        int b = rob(money, dp, 1, money.length-1);
        
        answer = Math.max(a, b);
        
        return answer;
    }
}

---

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