[동적 계획법] 도둑질 - Java 코드

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

코딩테스트 연습 - 도둑질

 

문제

 

이해

원형의 구조를 가지기 떄문에 첫번째집을 털면 마지막집을 털수없고,

두번째 집부터 털어야 마지막까지 비교가 가능해진다.

 

그러므로 두 가지 Case를 나눠서 순회하여 최댓값을 구하고, 두 경우 중 큰값을 반환해주면 된다.

 

중요한건 DP를 사용해야하므로,

두번의 케이스의 메모이제이션을 위해 Array를 만들어야한다.

(두번 돌려면 원본을 훼손하면 안되니깐..)

 

풀이

두 가지 case별로 배열을 2개 만들어서 각각의 인덱스마다 최대로 털 수 있는 돈의 합계를 저장해 나가면서 구해준다. 

 

n-2 까지 털었을때 합계 + n번째 집 돈을 더한값과

n-1 집까지 털었을때의 합계 중 큰 값을 비교해가면서

DP 배열을 초기화 해나간다.

// 도둑질
class Solution {
    public static int solution(int[] money) {
        int answer = 0;
        int len = money.length;
        // 처음 집 훔치고 마지막집을 훔치지 못하는 case와 , 그렇지 않은 케이스
        int[] case1 = new int[len];
        int[] case2 = new int[len];
        // case1은 Dp를 위해 0,1번 값을 모두 처음집값으로 셋팅
        case1[0] = money[0];
        case1[1] = money[0];
        //case2는 처음집을 안훔치므로 0값으로 셋팅
        case2[0] = 0;
        case2[1] = money[1];
        // DP - -2번째에 지금값을 더한것과 -1번째 집까지 훔친 경우를 비교하면서 어느집을 훔치는게 제일 큰지 합계를 저장
        for(int i=2; i<len; i++){
            case1[i] = Math.max(case1[i-2] + money[i], case1[i-1]);
            case2[i] = Math.max(case2[i-2] + money[i], case2[i-1]);
        }
        // 두 경우중 더 많이 훔치는 경우를 반환 
        //case1은 첫집을 턴경우이므로 마지막집은 접근하지않는다, len-2번째 인덱스와 비교
        answer = Math.max(case1[len-2], case2[len-1]);

        return answer;
    }
}