99클럽 코테 스터디 21일차 TIL: [프로그래머스] 도둑질

https://school.programmers.co.kr/learn/courses/30/lessons/42897

프로그래머스

 

dp로 풀 수 있는 문제로, 주요 포인트는 다음과 같다.

• 인접한 두 집을 털 수 없다. 따라서 i번째의 집까지 훔칠 수 있는 최대 금액을 dp[i]라고 했을 때, dp[i] = max(dp[i - 1], dp[i - 2] + arr[i])이다.
• 그런데 마지막 집에서 문제가 발생한다. 만약 첫 번째 집을 털었으면 마지막 집을 털 수 없고, 그렇지 않으면 마지막 집을 털 수 있다. 따라서 dp에 채워진 최대 금액이 첫 번째 집을 턴 경우를 포함하는지 그렇지 않은지 구분할 필요가 있다.
• 따라서 첫 번째 집을 터는 경우인 dp와 털지 않는 경우인 dp를 별도로 둔다. 그리고 마지막 집에 대한 점화식은 다음과 같다.
  • 첫 번째 집을 포함하는 경우, dp[i] = dp[i - 1]이다. (첫 번째 집을 포함했으면 마지막 집은 포함할 수 없으므로)
  • 첫 번째 집을 포함하지 않는 경우, dp[i] = max(dp[i - 1], dp[i - 2] + arr[i])이다.

import java.util.*;

class Solution {
    public int solution(int[] money) {
        
        int answer = 0;
        
        // 첫 번째 집을 터는 경우
        int[] dpWithFirst = new int[money.length];
        // 첫 번째 집을 털지 않는 경우
        int[] dpWithoutFirst = new int[money.length];
        
        dpWithFirst[0] = money[0];
        dpWithFirst[1] = Math.max(dpWithFirst[0], money[1]);
        dpWithoutFirst[1] = money[1];
        
        for (int i = 2; i < money.length; i++) {
            if (i == money.length - 1) {
                dpWithFirst[i] = dpWithFirst[i - 1];
                dpWithoutFirst[i] = Math.max(dpWithoutFirst[i - 1], dpWithoutFirst[i - 2] + money[i]);
                answer = Math.max(dpWithFirst[i], dpWithoutFirst[i]);
                break;
            } 
            dpWithFirst[i] = Math.max(dpWithFirst[i - 1], dpWithFirst[i - 2] + money[i]);
            dpWithoutFirst[i] = Math.max(dpWithoutFirst[i - 1], dpWithoutFirst[i - 2] + money[i]);
        }
        
        return answer;
    }
}