[Programmers] 도둑질 (Java)

1.  문제 링크

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

2.  문제

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

3.  제한사항

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

입출력 예

4.  소스코드

class Solution {
    public int solution(int[] money) {
        int[] withOne = new int[money.length], withoutOne = new int[money.length];
        withOne[0] = withOne[1] = money[0];
        withoutOne[1] = money[1];

        for(int idx = 2; idx < money.length; idx++) {
            withOne[idx] = Math.max(withOne[idx - 2] + money[idx], withOne[idx - 1]);
            withoutOne[idx] = Math.max(withoutOne[idx - 2] + money[idx], withoutOne[idx - 1]);
        }

        return Math.max(withOne[money.length - 2], withoutOne[money.length - 1]);
    }
}

5.  접근

• 하나의 집을 선택하면 인접한 집은 선택할 수 없기 때문에 한 집씩 건너뛰며 집을 선택할 수 있습니다.
• 즉, 현재 집을 선택하고 바로 이전 집이 아닌 그 전 집까지 최대로 훔칠 수 있는 돈과 합치는 경우와 현재 집을 선택하지 않고 바로 이전 집까지 최대로 훔칠 수 있는 돈을 선택하는 경우 두 가지가 존재합니다. 이에 따라 아래와 같은 점화식이 나올 수 있습니다.
  • dp[house] = max(dp[house - 2] + money[house], dp[house - 1])
• 그런데 또 두 가지 경우로 나눌 수 있습니다.
  • 1번 집을 선택하는 경우와 선택하지 않는 경우로 나눌 수 있습니다.
    • 1번 집을 선택하는 경우는 마지막 집을 선택할 수 없기 때문에 dp 배열에서 마지막 집까지의 최댓값을 이용할 수 없고 바로 이전 집까지의 최댓값을 이용합니다.
    • 1번 집을 선택하지 않는 경우는 마지막 집을 선택할 수 있으므로 dp 배열에서 마지막 집까지의 최댓값을 이용할 수 있습니다.
• 위 점화식을 이용하여 최댓값을 구합니다.