[프로그래머스][Java] Lv.4 도둑질

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0이상 1000이하인 정수입니다.

---

풀이과정

1) 점화식을 구하는 과정

//max 배열: i번째까지의 집까지 훔칠 수 있는 최댓값
int max[] = new int[money.length];

//max[0]은 0번째 집까지 훔칠 수 있는 최대의 돈
//0번 집의 돈을 훔친값 = money[0]
max[0] = money[0];

//max[1]은 1번째 집까지 훔칠 수 있는 최댓값이므로 (0번째 집을 선택 or 1번째 집을 선택)
max[1] = Math.max(money[0],money[1]);

//max[2]는 연속된 집은 털 수 없기 때문에 
//(0번째 집까지 훔친돈 최댓값 + 2번집 돈) or (1번째 집까지 훔친 돈) 을 선택해야 한다.
max[2] = Math.max(max[0]+money[2], max[1]);

// ...따라서 i번째 집까지 훔친 돈의 최댓값의 점화식은
max[i] = Math.max(max[i-2]+money[i],max[i-1]);

 

2) 처음 집과 마지막 집 둘 다 선택 되는 경우를 고려해야 한다.

첫번째 집과 마지막 집 둘 다 선택되는 경우는 없어야 하기 때문에 경우의 수를 나눠서 생각한다.

1. 첫번째 집을 무조건 방문하는 경우
2. 첫번째 집을 절대 방문하지 않는 경우

경우를 나눠 두가지 모두 계산을 한 뒤 더 큰 값을 마지막에 비교해주면 될 일이다.

첫 번째 집을 무조건 포함하는 경우	maxInclude[]
첫 번째 집을 절대 포함하지 않는 경우	maxExclude[]

---

전체 코드

class Solution {
    public int solution(int[] money) {
        
        int n = money.length; //집의 개수
        
        //집의 개수가 홀수개이면 집들이 원형으로 배치되어있기 때문에
        //처음집과 마지막 집을 동시에 선택할 수 없다.
        int[] maxInclude = new int[n]; // 첫번째 집을 무조건 포함하는 경우
        int[] maxExclude = new int[n]; // 첫번재 집을 무조건 빼는 경우
        
        maxInclude[0]=maxInclude[1]=money[0];
        maxExclude[1]=money[1];
        
        for(int i=2;i<n;i++){
            // i번째 집까지 훔칠 수 있는 돈의 최댓값은
            // maxMoney[i] = Math.max(maxMoney[i-1],maxMoney[i-2]+money[i])
            maxInclude[i]=Math.max(maxInclude[i-1],maxInclude[i-2]+money[i]);
            maxExclude[i]=Math.max(maxExclude[i-1],maxExclude[i-2]+money[i]);
        }
        
        return Math.max(maxInclude[n-2],maxExclude[n-1]);
    }
}