알고리즘(도둑질)

* 조건

1. 각각의 집들과 집에 존재하는 돈이 주어진다(money[])
2. 도둑은 인접한 집들은 털수 없다
3. 훔칠 수 있는 돈의 최댓값을 구한다

 

 

* 알고리즘

• DP

 

 

* 로직

• 첫 번째 집부터 털이를 시작하는 경우 -> 마지막 집은 털 수 없음(인접)
  • dp_first[0] = money[0], dp_first[1] = money[0] -> 인접하기 때문에 첫 번째 집을 털은 경우가 더 큼
  • dp_first[i] : i번째 집까지 훔칠 수 있는 돈의 최댓값을 갱신한다
    • 현재 집(i)을 털게 된다면 -> 이전에 인접하지 않은 집까지의 최댓값 + 현재 집의 돈
    • 털지 않는다면 -> 이전에 인접한 집까지의 최댓값
    • 위 두가지 중 큰 값을 넣어준다
• 첫 번째 집부터 털이를 시작하지 않는 경우 -> 마지막 집을 털 수 있음
  • dp_second[0] = 0, dp_second[1] = money[1]
  • 위의 로직과 같다
• dp_first와 dp_second의 마지막 값들 중에서 최댓값을 리턴한다

 

public class Problem_Thievery {

    public static void main(String[] args) {
        int[] money = {1, 2, 3, 1};
        int answer = solution(money);
        System.out.println(answer);
    }

    public static int solution(int[] money) {
        int answer;
        int[] dp_first = new int[money.length-1];
        int[] dp_second = new int[money.length];

        //첫번째 집부터 털이를 시작하는 경우 -> 마지막 집은 털 수 없음(인접)
        dp_first[0] = money[0];
        dp_first[1] = money[1]; //인접하기 때문에 첫번째 집을 털은 경우가 더 큼

        for(int i=2; i<dp_first.length; ++i){
            /*
                현재 i번째 집을 턴다면
                    -> (i-2)번째 집까지 얻을 수 있는 최대 금액과 더해준 값과
                현재 i번째 집을 털지 않고
                    -> (i-1)번째 집까지 얻을 수 있는 최대 금액 중에서 더 큰 값을 갱신한다
            */

            //현재 i번째 집까지 얻을 수 있는 금액의 최댓값을 갱신
            dp_first[i] = Math.max(dp_first[i-2] + money[i], dp_first[i-1]);
        }

        //첫번째 집을 털지 않는 경우 -> 마지막 집을 털 수 있음
        dp_second[0] = 0;
        dp_second[1] = money[1];
        for(int i=2; i<dp_second.length; ++i){
            dp_second[i] = Math.max(dp_second[i-2] + money[i], dp_second[i-1]);
        }
        answer = Math.max(dp_first[dp_first.length-1], dp_second[dp_second.length-1]);

        return answer;
    }
}