[프로그래머스/LV4] 도둑질 - DP (Java)

[프로그래머스/LV4] 도둑질

🙋‍♂️ 들어가며

조건은 다음과 같다.

3 <= N <= 1000000

0 <= money[i] <= 1000

우선 원형이기 때문에 절대 인접하면 안된다.

그러므로, 2가지 경우가 있겠다.

• 0번째 집을 선택했을 떄 -> idx : 0 ~ N-2
• 0번째 집을 선택 안하고, x번째 집을 선택했을 때 -> idx : x ~ N-1

집이 6개라 가정할 때 경우의 수는 다음과 같겠다

case-1 (0번째 집 선택)

1. ✅ ⬜ ✅ ⬜ ✅ ⬜

2. ✅ ⬜ ⬜ ✅ ⬜ ⬜

case-2 (x번째 집 선택)

1. ⬜ ✅ ⬜ ✅ ⬜ ✅

2. ⬜ ✅ ⬜ ⬜ ✅ ⬜

3. ⬜ ⬜ ✅ ⬜ ✅ ⬜

4. ⬜ ⬜ ✅ ⬜ ⬜ ✅
   
   

case-1의 testcase는 다음과 같겠다

{10, 1, 10, 1, 10, 1}

{10, 1, 1, 10, 1, 1}

case-2의 testcase는 다음과 같겠다

{1, 10, 1, 10, 1, 10}

{1, 10 1, 1, 10, 1}

{1, 1, 10, 1, 10, 1}

{1, 1, 10, 1, 1, 10}

이걸 계산하니 다음과 같은 점화식을 도출할 수 있게 되었다

✅ 정답 코드

class Solution {
    public int solution(int[] money) {
        int answer = 0;
        int N = money.length;
        
        // 1. 조기종료
        if (N == 1) {
            return money[0];
        }
        else if (N == 2) {
            int res = Math.max(money[0], money[1]);
            return res;
        }
        else if (N == 3) {
            int res = Math.max(money[0], Math.max(money[1], money[2]));
        }
        
        // 2. N >= 4
        int[] DP_0 = new int[N];
        int[] DP_x = new int[N];
        
        // 2-1. 0번째 집 선택
        DP_0[0] = money[0];
        DP_0[1] = money[0];
        for (int i = 2; i < N-1; i++) {
            DP_0[i] = Math.max(DP_0[i-1], DP_0[i-2] + money[i]);
        }
        
        // 2-2. 0번쨰 집 선택X
        DP_x[1] = money[1];
        DP_x[2] = Math.max(money[1], money[2]);
        for (int i = 3; i < N; i++) {
            DP_x[i] = Math.max(DP_x[i-1], DP_x[i-2] + money[i]);
        }
        
        // 3. 비교
        answer = Math.max(DP_0[N-2], DP_x[N-1]);
        return answer;
    }
}