[프로그래머스/DP] Level 4 도둑질 (JAVA)

문제

---

풀이

1차원 배열로 money가 주어지지만, 첫 번째와 마지막 집을 동시에 방문할 수 없다는 조건이 추가된 문제이다. 이 조건을 해결하기 위해서는 dp를 2차원 배열로 선언하고, 2가지 경우로 나누어서 값을 구해야 한다.

1. 마지막 집을 제외하는 경우: 첫 번째 집을 방문한다/안 한다를 보장하지는 않는다. 그냥 마지막 집만 제외하고 나머지 집들로만 최댓값을 구한다.
2. 첫 번째 집을 제외하는 경우: 역시 마지막 집을 방문해야 한다/아니다는 조건이 아니다.

또한, 연달아서 두 채의 집을 방문할 수 없는 조건에 의해, 3가지 경우의 수를 고려해서 최댓값을 찾아야 한다.

i번 집의 최댓값은 아래 세 가지 경우 중 최댓값이다.

1. i번 선택 X → dp[i-1]
2. i번 선택 + i-2번을 함께 선택 → dp[i-2] + money[i]
3. i번 선택 + i-3번을 함께 선택 → dp[i-3] + money[i]

i-3까지만 dp배열을 참조하는 이유는, dp[i-4]부터는 중간에 3개 이상의 집이 있어서 집을 추가로 선택할 수 있으므로, dp 배열의 각 값이 최댓값을 보장하지 않게 되기 때문이다.

이러한 과정을 코드로 나타내면 아래와 같다.

코드

class Solution {
    
    private static final int MAX = 1000000;
    private static final int LAST_NOT_VISITED = 0;
    private static final int FIRST_NOT_VISITED = 1;

    private int[][] dp = new int[2][MAX + 1];

    public int solution(int[] money) {
        dp(money);
        return Math.max(dp[LAST_NOT_VISITED][money.length - 1], dp[FIRST_NOT_VISITED][money.length]);
    }

    private void dp(int[] money) {
        dp[LAST_NOT_VISITED][1] = money[0];
        dp[LAST_NOT_VISITED][2] = money[1];
        dp[FIRST_NOT_VISITED][1] = 0;
        dp[FIRST_NOT_VISITED][2] = money[1];
        for (int i = 3; i <= money.length; i++) {
            dp[LAST_NOT_VISITED][i] = Math.max(dp[LAST_NOT_VISITED][i - 2] + money[i - 1],
                    Math.max(dp[LAST_NOT_VISITED][i - 3] + money[i - 1],
                            dp[LAST_NOT_VISITED][i - 1]));
            dp[FIRST_NOT_VISITED][i] = Math.max(dp[FIRST_NOT_VISITED][i - 2] + money[i - 1],
                    Math.max(dp[FIRST_NOT_VISITED][i - 3] + money[i - 1],
                            dp[FIRST_NOT_VISITED][i - 1]));
        }
    }
}