[프로그래머스][JAVA] 42897. 도둑질

💡 문제
도둑질 (https://school.programmers.co.kr/learn/courses/30/lessons/42897)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

📝 선행 개념

---

🤓 문제 풀이

🔨 문제 설명

도둑이 동그랗게 배치된 집들에서 훔칠 수 있는 돈의 최댓값을 구하는 문제입니다. 이 문제는 동적 계획법(Dynamic Programming, DP)을 사용하여 해결할 수 있습니다.

원형으로 배치된 집들을 보면 집들이 원형으로 배치되어 있으므로 첫 번째 집과 마지막 집이 연결되어 있다. 즉 즉, 첫 번째 집과 마지막 집은 동시에 털 수 없습니다

인접한 두 집을 털면 경보가 울림에서 인접한 두 집을 동시에 털 수 없으므로, 선택한 집이 연속되지 않도록 해야 합니다.

---

🔨 접근 방법

• 집들이 원형으로 배치:
  • 첫 번째 집과 마지막 집이 연결되어 있으므로, 첫 번째 집을 털면 마지막 집을 털 수 없고, 그 반대도 마찬가지입니다.
  • 이 문제를 두 가지 경우로 나눠서 풀 수 있습니다:
    • 첫 번째 집을 터는 경우
    • 첫 번째 집을 털지 않는 경우
• 동적 계획법(DP)을 이용한 해결:
  • dp[i]를 i번째 집까지 훔칠 수 있는 최댓값으로 정의합니다.
  • 각 경우에 대해 DP 테이블을 구성하여 최댓값을 계산합니다.
• 두 경우의 계산:
  • 첫 번째 집을 터는 경우: 마지막 집을 털 수 없으므로 money 배열의 범위는 [0, n-2]입니다.
  • 첫 번째 집을 털지 않는 경우: 첫 번째 집을 털 수 없으므로 money 배열의 범위는 [1, n-1]입니다.
  • 두 경우의 결과를 비교하여 최종 결과를 도출합니다.

---

🔨 문제 풀이 과정

• DP 배열 초기화 및 구성:
  • 첫 번째 집을 터는 경우:
    • dp1[i] = max(dp1[i-1], dp1[i-2] + money[i])
    • dp1[0] = money[0]
    • dp1[1] = max(money[0], money[1])
  • 첫 번째 집을 털지 않는 경우:
    • dp2[i] = max(dp2[i-1], dp2[i-2] + money[i])
    • dp2[1] = money[1]
    • dp2[2] = max(money[1], money[2])
• 결과 계산:
  • 두 경우에서 계산된 최댓값을 비교하여 최종 결과를 도출합니다.

---

🔨 동적 계획법(Dynamic Programming, DP)

동적 계획법(Dynamic Programming, DP)을 사용하는 이유는 주어진 문제의 성격과 제약 조건을 고려했을 때 DP가 적합한 해결 방법이기 때문입니다. 구체적으로, 이 문제에서 DP를 사용하는 이유는 다음과 같습니다:

• 첫 번째 집을 터는 경우:
  • dp1[i] = max(dp1[i-1], dp1[i-2] + money[i])
  • dp1[0] = money[0]
  • dp1[1] = max(money[0], money[1])
• 첫 번째 집을 털지 않는 경우:
  • dp2[i] = max(dp2[i-1], dp2[i-2] + money[i])
  • dp2[1] = money[1]
  • dp2[2] = max(money[1], money[2])

1. 최적 부분 구조 (Optimal Substructure)

DP를 사용할 수 있는 중요한 조건 중 하나는 "최적 부분 구조"입니다. 이는 문제의 최적 해가 부분 문제들의 최적 해로 구성될 수 있는 성질을 의미합니다. 이 문제의 경우, 각 집까지의 최댓값은 이전 집들까지의 최댓값을 이용하여 계산할 수 있습니다.

예를 들어, i번째 집까지의 최댓값을 계산할 때, 두 가지 선택이 있습니다:

• i번째 집을 털지 않는 경우: i-1번째 집까지의 최댓값이 그대로 유지됩니다.
• i번째 집을 터는 경우: i-2번째 집까지의 최댓값에 현재 집의 돈을 더한 값이 됩니다.

따라서, dp[i] = max(dp[i-1], dp[i-2] + money[i])라는 점화식을 사용할 수 있습니다.

2. 중복 부분 문제 (Overlapping Subproblems)

DP를 사용하는 또 다른 이유는 "중복 부분 문제"입니다. 이는 동일한 부분 문제들이 반복적으로 계산될 때 효율적으로 해결할 수 있는 성질을 의미합니다. 이 문제에서도 각 집까지의 최댓값을 계산하기 위해서는 이전 집들까지의 최댓값을 반복적으로 참조하게 됩니다.

동적 계획법은 이러한 중복 계산을 피하기 위해 이미 계산된 값을 메모이제이션 기법을 통해 저장하고, 필요할 때마다 재사용합니다. 이로 인해 계산의 효율성을 크게 높일 수 있습니다.

3. 문제의 제약 조건

문제에서 집의 개수는 최대 1,000,000개까지 될 수 있습니다. 이와 같은 큰 입력 크기에 대해 모든 가능한 조합을 일일이 계산하는 브루트 포스(Brute Force) 방법은 비효율적이며, 현실적으로 불가능합니다. 하지만 DP를 사용하면 시간 복잡도를 선형 시간으로 줄일 수 있어 대규모 입력에 대해서도 효율적으로 해결할 수 있습니다.

---

🔨 구현코드

class Solution {
    public int solution(int[] money) {
        int n = money.length;
        
        if (n == 3) {
            return Math.max(money[0], Math.max(money[1], money[2]));
        }
        
        // 첫 번째 집을 터는 경우
        int[] dp1 = new int[n-1];
        dp1[0] = money[0];
        dp1[1] = Math.max(money[0], money[1]);
        for (int i = 2; i < n-1; i++) {
            dp1[i] = Math.max(dp1[i-1], dp1[i-2] + money[i]);
        }
        
        // 첫 번째 집을 털지 않는 경우
        int[] dp2 = new int[n];
        dp2[1] = money[1];
        dp2[2] = Math.max(money[1], money[2]);
        for (int i = 3; i < n; i++) {
            dp2[i] = Math.max(dp2[i-1], dp2[i-2] + money[i]);
        }
        
        // 두 경우 중 최댓값 반환
        return Math.max(dp1[n-2], dp2[n-1]);
    }
}

---

📚 풀이 보완

코드 설명

• 기본 조건 처리:
  • 만약 집이 3개인 경우는 예외로 처리합니다.
• 첫 번째 집을 터는 경우:
  • dp 배열을 dp1로 정의하고, 마지막 집을 제외하고 계산합니다.
• 첫 번째 집을 털지 않는 경우:
  • dp 배열을 dp2로 정의하고, 첫 번째 집을 제외하고 계산합니다.
• 최종 결과 반환:
  • 두 경우에서 얻은 최댓값 중 더 큰 값을 반환합니다.
• 첫 번째 집을 터는 경우와 털지 않는 경우로 나누어 해결:
  • 집들이 원형으로 배치되어 있어 첫 번째 집과 마지막 집이 서로 연결되어 있습니다. 따라서 두 가지 경우로 나누어 DP를 적용합니다.
    • 첫 번째 집을 터는 경우: 마지막 집을 털 수 없으므로 [0, n-2] 범위의 집들만 고려합니다.
    • 첫 번째 집을 털지 않는 경우: 첫 번째 집을 털 수 없으므로 [1, n-1] 범위의 집들만 고려합니다.
• DP 배열 정의 및 초기화:
  • 각 경우에 대해 dp 배열을 정의하고, 초기값을 설정합니다.
• 점화식 적용:
  • 각 집에 대해 두 가지 선택지를 고려하여 최댓값을 계산합니다.
• 최종 결과 도출:
  • 두 가지 경우에서 계산된 최댓값을 비교하여 최종 결과를 반환합니다.

---

📍 Plus+

공간 복잡도

공간 복잡도는 알고리즘이 실행될 때 필요한 메모리 공간의 양을 나타냅니다. 이 문제의 경우, 동적 계획법을 사용하여 두 개의 dp 배열을 사용하고 있습니다.

• 첫 번째 집을 터는 경우:
  • dp1 배열은 n-1 크기입니다.
• 첫 번째 집을 털지 않는 경우:
  • dp2 배열은 n 크기입니다.

따라서, 전체 공간 복잡도는 두 배열의 크기 합이 됩니다. 하지만, 일반적으로 큰 항을 중심으로 공간 복잡도를 표현하므로 O(n)이 됩니다.

시간복잡도

시간 복잡도는 알고리즘이 실행되는 데 필요한 시간의 양을 나타냅니다. 이 문제에서, 동적 계획법을 사용하여 각 경우에 대해 한 번의 반복문을 통해 값을 계산합니다.

• 첫 번째 집을 터는 경우:
  • dp1 배열을 채우기 위해 n-1번의 연산이 필요합니다.
• 첫 번째 집을 털지 않는 경우:
  • dp2 배열을 채우기 위해 n-1번의 연산이 필요합니다.

각 경우에 대해 배열을 한 번씩 순회하므로, 시간 복잡도는 O(n)입니다.

요약

• 공간 복잡도: O(n)
  • 두 개의 dp 배열을 사용하여 n 또는 n-1 크기의 메모리를 사용합니다.
• 시간 복잡도: O(n)
  • 두 경우에 대해 각 배열을 한 번씩 순회하여 최댓값을 계산합니다.

문제 해결 과정 요약

1. 원형 배열의 특성:
   • 첫 번째 집과 마지막 집이 연결되어 있어 두 가지 경우로 나누어야 합니다: 첫 번째 집을 터는 경우와 첫 번째 집을 털지 않는 경우.
2. 동적 계획법 적용:
   • dp[i]를 i번째 집까지 훔칠 수 있는 돈의 최댓값으로 정의.
   • 첫 번째 집을 터는 경우는 [0, n-2] 범위, 첫 번째 집을 털지 않는 경우는 [1, n-1] 범위로 나누어 계산.
3. 점화식 사용:
   • dp[i] = max(dp[i-1], dp[i-2] + money[i])로 각 집까지의 최댓값을 계산.
4. 결과 비교:
   • 두 경우의 최댓값을 비교하여 최종 결과를 도출.

 

---

풀이 참고 로직