[lv4] 도둑질

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

 

시간 제한 빡빡한 원형 DP 문제다.

 

 

풀이

 

1. 원형 DP (0번째 집을 훔쳤으면, M-1번째 집을 훔칠 수 없음)

=> 배열 idx를 0 ~ M-2, 1 ~ M-1 까지 고려하는 경우로 나누어 DP를 2번 수행한다.

 

2. DP기록

 

dp[i][0], dp[i][1]을 각각 i번째 집을 안훔치는/훔치는 경우로 두었는데, 이것만으로도 시간 초과가 난다.

=> 배열 대신에 변수에 기록하고, swap하며 탐색한다.

 

 

 

시간 초과 코드

// 시간 초과 1. 2차원 DP 배열 2개 + money 배열 2개 사용

 

import java.util.*;

class Solution {
    public int solution(int[] money) {
        int M = money.length;
        int answer = 0;
        
        int[] m1 = new int[M-1];
        for(int i=0; i<M-1; i++)
            m1[i] = money[i];
        
        int[] m2 = new int[M-1];
        for(int i=1; i<M; i++)
            m2[i-1] = money[i];
        
        int[][] dp1 = new int[M-1][2];
        dp1[0][1] = m1[0];
        
        int[][] dp2 = new int[M-1][2];
        dp2[0][1] = m2[0];
        
        return Math.max(tryDP(dp1, m1), tryDP(dp2, m2));
    }
    
    static int tryDP(int[][] dp, int[] m) {
        int M = m.length;
        
        for(int i=1; i<M; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + m[i];
        }
        
        return Math.max(dp[M-1][0], dp[M-1][1]);
    }
}

// 시간 초과 2. 2차원 DP 배열 2개 사용

 

import java.util.*;

class Solution {
    public int solution(int[] money) {
        int M = money.length;
        
        int[][] dp1 = new int[M][2];
        dp1[0][1] = money[0];
        
        int[][] dp2 = new int[M][2];
        dp2[1][1] = money[1];
        
        int l = tryDP(dp1, money, 0, M-2);
        int r = tryDP(dp2, money, 1, M-1);
        
        return Math.max(l, r);
    }
    
    static int tryDP(int[][] dp, int[] m, int st, int ed) {
        int M = m.length;
        
        for(int i=st+1; i<=ed; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + m[i];
        }
        
        return Math.max(dp[ed][0], dp[ed][1]);
    }
}

 

제출 코드

import java.util.*;

class Solution {
    public int solution(int[] money) {
        int M = money.length;

        int l = tryDP(money[0], 0, M-2, money);
        int r = tryDP(money[1], 1, M-1, money);

        return Math.max(l, r);
    }

    static int tryDP(int y, int st, int ed, int[] m) {
        int M = m.length;

        // y/n : i번째 집 돈을 훔치는/안훔치는 경우
        int n = 0;

        for(int i=st+1; i<=ed; i++) {
            int tmp = n;
            n = Math.max(y, n);
            y = tmp + m[i];
        }

        return Math.max(y, n);
    }
}