99클럽 코테 스터디 21일차 TIL - DP (프로그래머스 '도둑질')

항해99 코테 스터디 21일차 문제인 프로그래머스의 '도둑질'은 원형으로 이어진 집들을 도둑질하여 얻을 수 있는 가장 큰 금액을 구하는 문제이다. 난이도는 레벨4이며 다이나믹 프로그래밍을 통해 해결할 수 있다.

 

오늘의 문제 - 도둑질 문제 정보

문제 키워드

- DP

난이도

- Level 4

 

문제 요약

• 모든 집은 원형으로 이어져 있으며, 연속된 두 집을 터는 경우 경보가 울린다.
• 경보가 울리지 않고 도둑질을 할 때, 얻을 수 있는 가장 큰 금액을 구하여라.

 

문제 풀이 과정  

• 원형으로 이어져 있으므로 첫번째 집을 터냐 마냐에 따라서 마지막 집을 털 수 있는지가 달라진다.
• 따라서 첫번째 집을 터는 경우와 안 터는 경우로 나누어서 DP 배열 값들을 구해야 한다.
• dp[i] = (dp[i-2] + money[i], dp[i-1])
  • i번째 집까지 얻을 수 있는 최대 금액 -> 직전 집 안털고 현재 집 터는 경우, 직전 집 털고 현재 집 안 터는 경우 중 큰 값
• 다만, 마지막 집의 값을 구할 때는 첫번째 집을 털었는지에 따라 달라지므로 따로 계산한다.

코드

class Solution {
    public int solution(int[] money) {
        int N = money.length;
        
        // dp1: 0번째집 안턴 경우의 결과들, dp2: 0번째집 턴 경우의 결과들
        int[] dp1 = new int[N];
        int[] dp2 = new int[N];
        
        // dp[i] = max(dp[i-2] + money[i], dp[i-1]) 
        // -> 직전 집 안 털고 현재 집을 턴 경우와 턴 경우 중 큰 값
        
        // 0번째 집 안털음
        dp1[0] = 0; dp1[1] = money[1];
        
        // 0번째 집 털음 -> 1번째 집 못털음
        dp2[0] = money[0]; dp2[1] = dp2[0];
        
        // 2번째 ~ N-1번째 집까지 dp값을 구함
        for(int i=2; i<N-1; i++) {
            dp1[i] = max(dp1[i-2] + money[i], dp1[i-1]);
            dp2[i] = max(dp2[i-2] + money[i], dp2[i-1]);
        }
        
        // N번째 집 결과 중 큰 값이 정답
        // 1. 0번째 집 안 턴 경우 -> N번째 집 털 수도 있음
        dp1[N-1] = max(dp1[N-3] + money[N-1], dp1[N-2]);
        
        // 2. 0번째 집 턴 경우 -> N번째 집 못 털음
        dp2[N-1] = dp2[N-2];
        
        return max(dp1[N-1], dp2[N-1]);
    }
    
    private int max(int a, int b) {
        return a >= b? a : b;
    }
}

• 시간복잡도: O(N)
• 공간복잡도: O(N)