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

프로그래머스 Lv.4 - 도둑질

요구사항

• 원형으로 배치된 집에서 인접한 집은 털 수 없을 때 훔칠 수 있는 최대 금액을 구하는 문제
• 첫 번째 집과 마지막 집은 인접하므로 동시에 털 수 없음

접근 방식

원형 구조라 첫 번째 집과 마지막 집을 동시에 선택할 수 없는 제약을 두 번의 DP 로 해결했다.

핵심 아이디어

경우 1: 첫 번째 집 포함 (마지막 집 제외)
→ dp1을 money[0] ~ money[n-2] 범위로 실행

경우 2: 마지막 집 포함 (첫 번째 집 제외)
→ dp2를 money[1] ~ money[n-1] 범위로 실행

정답 = max(dp1[n-2], dp2[n-1])

점화식

dp[i] = max(dp[i-2] + money[i], dp[i-1])
→ 현재 집을 털거나(dp[i-2] + money[i]) 안 털거나(dp[i-1])

"첫 번째, 마지막 집 둘 다 안 터는 경우"는 따로 처리 불필요

• dp2[0] = 0 으로 시작 = 첫 번째 집을 아예 고려하지 않음
• DP는 최댓값을 누적하므로 둘 다 안 터는 게 최적이면 자연스럽게 반영됨

코드

import java.util.*;

class Solution {
    public int solution(int[] money) {
        int n = money.length;

        // 경우 1: 첫 번째 집 포함, 마지막 집 제외
        int[] dp1 = new int[n];
        dp1[0] = money[0];
        dp1[1] = dp1[0];
        for (int i = 2; i < n-1; i++) {
            dp1[i] = Math.max(dp1[i-2] + money[i], dp1[i-1]);
        }

        // 경우 2: 마지막 집 포함, 첫 번째 집 제외
        int[] dp2 = new int[n];
        dp2[1] = money[1];
        for (int i = 2; i < n; i++) {
            dp2[i] = Math.max(dp2[i-2] + money[i], dp2[i-1]);
        }

        return Math.max(dp1[n-2], dp2[n-1]);
    }
}

느낀점

• 처음에는 이중 반복문으로 접근했지만 시간초과가 날 것을 인지하고 점화식으로 전환했다.
• 원형 DP의 핵심은 두 번 DP를 돌리는 것 이다.
  첫 번째 집 포함 / 마지막 집 포함으로 나눠서 각각 최적값을 구하면 된다.
• dp2[0] = 0 으로 시작하면 자연스럽게 첫 번째 집을 제외할 수 있다.
• "둘 다 안 터는 경우"는 DP의 최댓값 누적 특성상 따로 처리하지 않아도 된다.