[JAVA] 프로그래머스 : 도둑질 (코딩테스트 고득점 kit > 동적계획법(Dynamic Programming))

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

코딩테스트 연습 - 도둑질

[LEVEL 4]

처음에 문제를 이해할 때, 인접한 집이 아니면 된다는 생각에 홀수 또는 짝수 인덱스로 되어있는 집끼리 money 값을 더해서 구했었으나 반례를 찾아냄
money = {1, 1, 1, 8, 1, 1, 7, 1, 1} 이런 경우 두 칸이 띄어져있더라도 8,7을 훔치는게 더 나음으로..

 

해결 방안

1. 처음 집을 훔치고 마지막 집을 안 훔칠때와 처음 집을 안 훔칠 때 2가지 경우로 나누어서 구하였음

2. 2가지 경우를 각각 money 배열의 인덱스만큼 왔을 때 누적시킨 money값들의 max 값을 구하여 메모제이션 해줌

3. 2가지 경우의 마지막 인덱스 배열의 max 값을 구하여 answer에 저장함

 

코드

// 도둑질
class Solution {
    public int solution(int[] money) {
        int answer = 0;
        
        // 처음 집 훔치고 마지막 집 안훔칠 때
        int[] stealMoney1 = new int[money.length-1];
        // 처음 집 안 훔칠 때
        int[] stealMoney2 = new int[money.length];
        
        stealMoney1[0] = money[0];
        stealMoney1[1] = money[0];
        stealMoney2[0] = 0;
        stealMoney2[1] = money[1];
        
        for(int i=2; i<stealMoney1.length; i++){
            stealMoney1[i] = Math.max(stealMoney1[i-2] + money[i], stealMoney1[i-1]);
        }
        
        for(int i=2; i<stealMoney2.length; i++){
            stealMoney2[i] = Math.max(stealMoney2[i-2] + money[i], stealMoney2[i-1]);
        }
        
        answer = Math.max(stealMoney1[stealMoney1.length-1], stealMoney2[stealMoney2.length-1]);
        
        return answer;
    }
}