[프로그래머스] 도둑질 (DP)

문제 소개

오늘 풀었던 도둑질 - 프로그래머스 문제를 정리합니다.
이 문제는 원형으로 연결된 집들에서 인접한 집을 동시에 털 수 없는 제약 하에, 도둑이 훔칠 수 있는 최대 금액을 구하는 문제입니다.
핵심은 첫 집과 마지막 집이 연결되어 있다는 제약을 어떻게 풀어낼지 입니다.

문제 링크: 도둑질 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 집이 일직선인 경우에 DP로 해결
2. 하지만 이 문제는 원형 구조이기 때문에 첫 번째 집과 마지막 집이 서로 인접
   • 첫번째 집을 고려하면 무조건 마지막 집은 제외해야함
3. 따라서 첫 집을 고려하는 경우 / 고려하지 않는 경우로 나누어 각각 계산
   • 도둑질한 최대 금액에 첫 집이 포함되는지 안 되는지 모르지만,
     첫 집을 고려할 때 아예 마지막 집을 제외하면 첫 집-마지막 집(인접한 집)을 선택하는 경우는 없음 
4. 두 경우의 최댓값 중 큰 값을 정답으로 선택

---

해결 과정 및 코드

핵심 아이디어

1. 한 번에 모두 고려하기 어렵고, 두 가지 경우로 나눔
   • Case 1: 첫 집을 포함, 마지막 집은 털 수 없음 → 범위: 0 ~ n-2
   • Case 2: 첫 집을 제외, 마지막 집 포함 가능 → 범위: 1 ~ n-1
2. 각 경우마다 일진선으로 존재하는 집 도둑 DP (dp[i] = max(dp[i-1], dp[i-2] + money[i])) 적용
3. 공간을 절약하기 위해 이전 두 개 값(prev1, prev2)만 저장하며 순회

코드

시간 복잡도 :O(N)
이유: 두 가지 경우에 대해 각각 한 번씩 순회하며 DP 수행

 

class Solution {
    public int solution(int[] money) {
        int n = money.length;
        
        // 집이 3개일 경우 예외 처리
        if (n == 3) {
            return Math.max(money[0], Math.max(money[1], money[2]));
        }
        
        // Case 1: 첫 집을 털고 마지막 집은 안 털기 (0 ~ n-2)
        int case1 = robHouse(money, 0, n - 2);
        
        // Case 2: 첫 집 안 털고 마지막 집은 털기 (1 ~ n-1)
        int case2 = robHouse(money, 1, n - 1);
        
        return Math.max(case1, case2);
    }

    // DP로 해당 구간 내 최대 돈을 계산하는 함수
    private int robHouse(int[] money, int start, int end) {
        int prev2 = money[start];
        int prev1 = Math.max(money[start], money[start + 1]);

        for (int i = start + 2; i <= end; i++) {
            int current = Math.max(prev1, prev2 + money[i]);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}