[프로그래머스] 도둑질 (자바) / DP

문제 설명

 

입력&출력

 

문제풀이

class Solution {
    public int solution(int[] money) {
        int answer = 0;
        //0부터 시작 맨 마지막 제외
        int[] dp0 = new int[money.length-1];
        //1부터 시작 맨 마지막 포함
        int[] dp1 = new int[money.length];
        
        dp0[0] = money[0];
        dp0[1] = money[0];
        
        dp1[0] = 0;
        dp1[1] = money[1];
        for(int i = 2 ; i < money.length-1;i++ ){
            dp0[i] = Math.max(dp0[i-2]+money[i],dp0[i-1]);
        }
        
        for(int i = 2; i < money.length;i++){
            dp1[i] = Math.max(dp1[i-2]+money[i],dp1[i-1]);
        }
        
        
        // int sum1=0;
        // int sum2=0;
        // for(int i = 0 ; i < money.length/2;i++){
        //     sum1+=money[2*i];
        //     sum2+=money[2*i+1];
        // }
        // answer = Math.max(sum1,sum2);
        return Math.max(dp0[money.length-2],dp1[money.length-1]);
    }
}

 

※ 내 생각

이 문제는 DP를 활용하는 문제입니다.
인접한 원소를 포함시키지 못하기 때문에,
맨 처음에 첫번째 원소를 선택할 것인지, 두번째 원소부터 시작할 것인지를 선택해야 합니다.

2개의 dp의 경우로 각각 for문을 돌려줍니다.
dp는 2칸 전+현재의 money와 바로 이전의 dp와 비교해서 max값을 선택하면 됩니다.