문제 바로가기

접근방법

사실 몇분 고민하다 내 머리에선 답이 안나와서(dp는 항상 그렇더라...) 다른 사람들의 풀이를 바로 봤다.

먼저 dp배열을 두개 만들어야하는데, 그 이유는 맨앞집을 훔치면 맨뒷집을 못훔치고, 맨앞집을 안훔치면 맨뒷집을 훔칠 수 있기 때문이다.
그래서 맨앞집을 훔치는 dp배열 하나, 맨뒷집을 훔치는 dp배열 하나.
이렇게 두개의 dp배열을 만들어주고,

옆집만 안겹치면 되니까
1. (현재 집)+(앞앞집)
2. (앞집)
이렇게 두개를 계속 비교해나가면서 dp배열에 더해주면 된다.

정답코드

import java.io.*;
import java.util.*;

class Solution {
    public int solution(int[] money) {
        int answer = 0;
        int len = money.length;
        
        int[] first=new int[len];
        int[] second=new int[len];
        
        first[0]=first[1]=money[0];
        second[1]=money[1];
        
        for(int i=2;i<len;i++){
            first[i]=Math.max(first[i-1],first[i-2]+money[i]);
            second[i]=Math.max(second[i-1],second[i-2]+money[i]);
        }
        
        answer=Math.max(first[len-2], second[len-1]);
        return answer;
    }
}