동적계획법(Dynamic Programming) 도둑질 자바

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

프로그래머스

 

class Solution {
    public int solution(int[] money) {
        int answer = 0;
        
        //바로 money로 받아오면 dp_first와 dp_second는 각각 money 배열을 새로운 배열로 복사하는 것이 아니라,
        // money 배열 자체를 가리키게 됩니다. 즉, dp_first, dp_second, money가 모두 같은 배열을 공유하게 됩니다.
        //int[] dpFirst = money;
        //int[] dpSecond = money;
        
		int[] dpFirst = new int[money.length];
        int[] dpSecond = new int[money.length];
        
        //dpFirst 은 첫번째 값을 선택했을 경우이다.
        //첫번째 값을 살리면 2번째 값을 죽인다.
        //네번째 값부터 반복문이 돌아야 하니까 세번째 값을 넣어준다
        //세번째 값은 쓸 수 있으므로? 첫번째 값과 세번째 값을 합친 값이다
        for(int i = 0; i < money.length; i++) {
            dpFirst[i] = money[i];
            dpSecond[i] = money[i];
        }
        
        dpFirst[1] = -1;
        dpFirst[2] += dpFirst[0];
        
        //dpSecond는 두번째 값을 살리는 경우이다.
        //두번째 값을 살리면 첫번째 값을 쓰지 못한다
        //비교를 4번째 값부터 시작하는데 세번째 값은 못쓰니가 무시? 
        dpSecond[0] = -1;
        
          // 집은 무조건 3개 이상이라는 조건.
        // 기준 값에서 두개 전이랑 세개 전을 비교해서 높은 값을 넣어준다.
        //그러므로 i는 3부터 시작해야 네번째 값과 두번째,첫번째 값을 비교할 수 있다.
        for(int i = 3; i < money.length; i++){
            dpFirst[i] += Math.max(dpFirst[i-2], dpFirst[i-3]);
            dpSecond[i] += Math.max(dpSecond[i-2], dpSecond[i-3]);
        }
        
         //dpFirst에서는 첫번째를 살렸기 때문에 첫번째와 연결되어 있지 않은 가장 먼 두 수를 비교한다.
        //money의 마지막에서 하나 전, 마지막에서 두개 전을 비교
        int firstMax = Math.max(dpFirst[money.length-2],dpFirst[money.length-3]);
        
         //dpSecond에서는 두번째를 살렸기 때문에 두번째와 연결되어 있지 않은 마지막 값과 마지막 전 값을 비교
        int secondMax = Math.max(dpSecond[money.length-1],dpSecond[money.length-2]);
        
        //두개 중에 더 큰값이 결과
        answer = Math.max(firstMax, secondMax);
        
        return answer;
    }
}