프로그래머스 - 도둑질 - DP - Java

1. 문제

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

2-1. [내] 풀이

이전에 풀었던 RGB 거리 2 와 비슷한 문제였다. 즉 1번집과 N번집이 같지 않을려면 두 가지로 나눠서 풀어야한다.

• 1번집을 안 털면 -> N번집 텀
• 1번집 털면 -> N번집 안 텀

1. 1번집을 털어
   1번집을 안 털 경우 dp[1] = money[1]로 두었고, end_index를 N-1까지로 두어서 N번째 집은 탐색하지 않는다.

2. 1번집을 안 털어
   1번집을 안털면 dp[1] = 0으로 두고 진행하였다. 처음에 dp[1] = Integer.MIN_VALUE로 두었다가 이 경우에는
   1번집 X 2번집과 3번집을 털 경우에서
   2번집 2 3번집 3이여도 점화식의 진행에 따라
   dp[3] = MAX(dp[2], money[3] + Integer.MIN_VALUE)때문에 dp[2]가 정답이 되어버린다. 따라서 dp[1] = 0이고 end_index를 n으로 두어 n번집까지 털도록 진행하였다.

3-1. [내] 코드

class Solution {
    public int solution(int[] money) {
        int answer = 0;
        int n = money.length;
        
        int dp[] = new int[n+1];
        
        for(int i = 0; i <= 1; i++){
            int end_index;
            
            if(i == 0){ // 1번집 안 털 경우
                //dp[1] = Integer.MIN_VALUE;
                dp[1] = 0;
                end_index = n;
                
            } else{ // 1번집 털 경우
                dp[1] = money[0];
                end_index = n-1;
            }
            
            for(int j = 2; j <= end_index; j++){
                dp[j] = Math.max(dp[j-2] + money[j-1], dp[j-1]);
            }
            
            answer = Math.max(answer, dp[end_index]);
        }
        return answer;
    }
}

---

2-2. 📢[코딩테스트 합격자 되기] 풀이

편의상 1번집 index를 0이라고 생각하자.
dp를 두 개로 놓고 풀어서

dp1[] : 1번집 털 경우
dp2[] : 1번집 안 털 경우

1. 1번집을 털 경우 -> 3번집 까지만 순회하는 것이고 이 경우 2번집을 못털기 때문에 dp[2번집]의 경우도 1번집의 money로 설정해 주는 것이다.

dp1[0] = money[0]
dp1[1] = money[0]

for(int i = 2; i < n-1; i++) // 3번집 까지만 순회.(index기준이기 때문에 3번집 index는 2가 될 것이다.)

2. 1번집을 안 털 경우 -> dp[1번집]은 0이 될 것이기 때문에 따로 설정하지 않아도 된다.

dp2[1] = money[1] // 2번집의 dp만 money[1]로 초기화.
for(int i = 2; i < n; i++) // 4번집까지 순회.

3. 마지막으로 두 개의 dp중에서 최댓값을 찾으면 된다.

answer = Math.max(dp1[n-2], dp2[n-1]);

3-2. [코딩테스트 합격자 되기] 코드

class Solution {
    public int solution(int[] money) {
        int n = money.length;
        int dp1[] = new int[n]; // 첫 번째 집 O (첫 번째 집 index = 0)
        int dp2[] = new int[n]; // 첫 번째 집 X
        
        // 1. 첫 번째 집 털 경우 -> 2번째집 못 터니까 두개의 dp의 값은 money[0]이다.
        dp1[0] = money[0];
        dp1[1] = money[0];
        for(int i = 2; i < n-1; i++){
            dp1[i] = Math.max(dp1[i-1], dp1[i-2] + money[i]);
        }
        
        // 2. 첫 번째 집 안 털면 -> dp2[0]의 값은 0이니까 따로 설정하지 않아도 됨. 그리고 마지막 집까지 순회
        dp2[1] = money[1];
        for(int i = 2; i < n; i++){
            dp2[i] = Math.max(dp2[i-1], dp2[i-2] + money[i]);
        }
        
        return Math.max(dp1[n-2], dp2[n-1]);
    }
}