[코딩테스트] Java 도둑질

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

원형으로 이루어진 집들에서 이웃집 체크를 할 때에 첫번째 집과 마지막 집을 체크하는 것이 문제였습니다. 이를 위해 동적 계획법을 두가지로 나누어 두 부분의 최댓 값중 더 큰 값을 반환하는 로직으로 문제를 해결하였습니다.

소스코드

class Solution {
    
    public int solution(int[] money) {
        int n = money.length;
        /* 
         * 첫번째 집을 포함하고 마지막 집을 빼는 경우
         * n까지 고려했을 때의 돈의 최댓값
         */ 
        int[] dp_includeFirst = new int[n]; 
        dp_includeFirst[0] = money[0];
        dp_includeFirst[1] = Math.max(money[1], money[0]);
        for(int i = 2; i < n-1; i++) {
            dp_includeFirst[i] = Math.max(money[i] + dp_includeFirst[i-2], dp_includeFirst[i-1]);
        }
        
        /* 
         * 첫번째 집을 제외하고 마지막 집을 선택하는 경우
         * n까지 고려했을 때의 돈의 최댓값
         */ 
        int[] dp_excludeFirst = new int[n]; 
        dp_excludeFirst[0] = 0;
        dp_excludeFirst[1] = money[1];
        for(int i = 2; i < n; i++) {
            dp_excludeFirst[i] = Math.max(money[i] + dp_excludeFirst[i-2], dp_excludeFirst[i-1]);
        }
        
        return Math.max(dp_excludeFirst[n-1], dp_includeFirst[n-2]);
    }
}

코드 설명

첫 번째 집을 포함하고 마지막 집은 제외.

 

• dp_includeFirst[i]: 0번째 집부터 i번째 집까지 고려했을 때, 훔칠 수 있는 최대 금액.
• 초기값:
  • 첫 번째 집(money[0])은 반드시 포함됨: dp_includeFirst[0] = money[0].
  • 두 번째 집은 첫 번째 집과 비교해 더 큰 금액 선택: dp_includeFirst[1] = Math.max(money[1], money[0]).
• for (int i = 2; i < n-1; i++) { dp_includeFirst[i] = Math.max(money[i] + dp_includeFirst[i-2], dp_includeFirst[i-1]); }
  • i번째 집을 포함하거나 포함하지 않는 경우 중 최대값 계산:
    • money[i] + dp_includeFirst[i-2]: 현재 집(i)을 포함하고, i-2번째 집까지의 최대값을 더함.
    • dp_includeFirst[i-1]: 현재 집을 포함하지 않고, i-1번째 집까지의 최대값.
  • 마지막 집(n-1)은 포함되지 않으므로 제외.

첫 번째 집을 제외하고 마지막 집을 포함.

 

• dp_excludeFirst[i]: 첫 번째 집을 제외하고, 1번째 집부터 i번째 집까지 고려했을 때의 최대 금액.
• 초기값:
  • 첫 번째 집은 제외되므로, dp_excludeFirst[0] = 0.
  • 두 번째 집은 money[1]으로 초기화: dp_excludeFirst[1] = money[1].
• for (int i = 2; i < n; i++) { dp_excludeFirst[i] = Math.max(money[i] + dp_excludeFirst[i-2], dp_excludeFirst[i-1]); }
  • 마지막 집(n-1)까지 포함.
• return Math.max(dp_excludeFirst[n-1], dp_includeFirst[n-2]);
  • 최대값 반환합니다.