프로그래머스 - 도둑질 (Level 3)

dp로 안 풀어보려고 홀수냐 짝수냐로 나눠서 도전해 봤지만 오류가 생김

-> 무조건 홀수거만 털거나 짝수거만 털 필요가 없었음

-> 홀수로 털다가 3칸 건너뛰어서 짝수로 털수도 있어서

 

 

결국 dp로 풀이

1. 첫번째 집을 털 경우와 안 털 경우로 나눠서 풀이

2. 

class Solution {
    public int solution(int[] money) {
        int len=money.length;
       //첫번째 집을 털 경우 -> 마지막 집 포함 불가
        int[] dp=new int[len-1];
        dp[0]=money[0];
        dp[1]=money[0];
        for(int i=2;i<len-1;i++){
            dp[i]=Math.max(dp[i-2]+money[i],dp[i-1]);//인접한 집 안털고 두군데가 크냐 한곳 턴게 더 크냐 비교 후 담기
        }
        //첫번째 집을 안 털 경우 -> 마지막 집 포함 가능
        int[] dp1=new int[len];
        dp1[0]=0;
        dp1[1]=money[1];
        for(int i=2;i<len;i++){
            dp1[i]=Math.max(dp1[i-2]+money[i],dp1[i-1]);//인접한 집 안털고 두군데가 크냐 한곳 턴게 더 크냐 비교 후 담기
        }
        return Math.max(dp[len-2],dp1[len-1]);//둘 중에 최대값 반환
    }
}