[Programmers/Level 4] 도둑질(Java)

문제 링크

프로그래머스

 

문제

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

 

 

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

 

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

 

예제 입력 1

4
1 2 3 1

예제 출력 1

4

 

알고리즘 분류

• 다이나믹 프로그래밍

 

풀이

첫 집을 터는 경우와 안 터는 경우로 나눈다.

첫 집을 털면 둘째 집은 털면 안 되므로 dp[0]과 dp[1]을 money[0]으로 초기화한다.

첫 집을 털지 않으면 둘째 집을 털어야 하므로 dp[1]을 money[1]로 초기화한다.

세 번째 집부터 터는 경우와 안 터는 경우, 그러니까 전전 집까지 턴 경우와 전 집까지 턴 경우를 비교하고, 둘 중 최댓값 + 현재 집이 보유한 돈이 현재까지 집을 털었을 때 보유할 수 있는 돈의 최댓값이 된다.

첫 집을 털면 마지막 집은 털면 안 된다. 따라서 dp[N - 2]까지 도달했을 때 돈의 최댓값을 구할 수 있다.

첫 집을 털지 않으면 마지막 집은 털어도 된다. 따라서 dp[N - 1]까지 도달했을 때 돈의 최댓값을 구할 수 있다.

첫 집을 털었을 때의 dp[N - 2]와 첫 집을 털지 않았을 때의 dp[N - 1] 둘 중 최댓값이 도둑이 훔칠 수 있는 돈의 최대치가 된다.

 

해결 완료 시각

 

코드

import java.util.*;

class Solution {
    
    private static int N;
    private static int[][] dp;
    
    public int solution(int[] money) {
        N = money.length;
        dp = new int[2][N];
        
        // 집이 3개면 한 채만 털 수 있다.
        if (N == 3) {
            return Math.max(Math.max(money[0], money[1]), money[2]);
        }
        
        // 첫 집을 터는 경우
        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]);
        }
        
        // 첫 집을 안 터는 경우
        dp[1][1] = money[1];
        for (int i = 2; i < N; i++) {
            dp[1][i] = Math.max(dp[1][i - 1], dp[1][i - 2] + money[i]);
        }
        
        return Math.max(dp[0][N - 2], dp[1][N - 1]);
    }
}