AlgorithmProgrammers

프로그래머스 도둑질

, , ,

1. 문제 링크

1.1. 프로그래머스 도둑질 문제

2. 문제 조건

2.1. 문제 설명

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

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

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

2.2. 제한사항

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

2.1. 컴퓨팅적 사고

훔친 비용의 값을 점진적으로 사용하기때문에 DP로 풀면 되겠다 라는 생각을 하게 되었습니다.

  • 첫번째집을 훔치는 경우 VS 첫번째집을 훔치지 않는 경우
    훔치는 경우의 수에 따라서 DP를 나누어서 값을 계산하였습니다.

첫번째 집을 훔치는 경우

첫번째집을 훔쳤을 경우에는 dp[0] = 첫번째집의 비용을 저장시켜줍니다.
첫번째집을 훔쳤을때에는 인접한 두번째집은 훔칠수 없습니다. 따라서 첫번째집을 훔치는경우는 두번째집을 선택할수없기때문에 두번째집도 지금까지 가장 큰 첫번째집 돈을 넣어줍니다. dp[1] = 첫번째 집의 비용

여기서 length의 범위를 -1을 해주게 되는데 첫번째집을 선택하게 될 경우 마지막에 있는 집은 방문을 하지않는것이 확실하기때문에 -1로 마지막 길이 이전까지만 순회시켜주었습니다.

첫번째 집을 훔치지 않는 경우
첫번째 집을 훔치지 않는 경우는 첫번째집은 0의 값을 넣어주게 됩니다.
dp1[0] = 훔치지 않으므로 0
두번째 집은 기존의 money[1]의 값을 넣어주게 되면서 이제 모든 비용을 구해주면됩니다.

이제 모든 비용을 구하기 위해서는 값을 누적해서 더해주면서 가장 큰 값으로 업데이트를 시켜줍니다. 즉, 최댓값을 구하기 위해서 Math.max() 함수를 사용하였습니다.

결, dp[길이-2], dp1[길이-1]에 집을 훔쳤을때, 훔치지 않았을때의 최대값이 저장되어 있을 것입니다. 그래서 dp의 비용과 dp1의 최댓값을 다시 구해주어 값을 리턴해주면 원하는 값을 찾을 수 있습니다.

이 문제의 핵심은 인접했을때의 경우의 수와 첫번째 집을 훔친 경우와 훔치지 않는 경우를 찾아내는것이 중요합니다.

2.2. 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class 도둑질 {
    static int[][] dp;
    public static void main(String[] args) {

        int[] money = {1,2,3,1};
        int[] dp = new int[money.length];
        int[] dp1 = new int[money.length];

        //첫번째 집을 훔치는 경우
        dp[0] = money[0]; // 첫번째집의 돈 훔치기
        dp[1] = money[0]; // 첫번째집을 훔치는경우는 두번째집을 선택할수없기때문에 두번째집도 지금까지 가장 큰 첫번째집 돈을 넣어준다.

        //첫번째 집을 훔치지 않는 경우
        dp1[0] = 0;     //첫번째집 훔치지않으므로 0
        dp1[1] = money[1]; //두번째집은 훔치는 가격

        for(int i=2; i<money.length-1; i++){
            dp[i] = Math.max(dp[i-2] + money[i], dp[i-1]);      // 1번째 세번째 훔치는 경우
        }

        for(int i=2; i<money.length; i++){
            dp1[i] = Math.max(dp1[i-2] + money[i], dp1[i-1]);
        }
        System.out.println(Math.max(dp[money.length-2], dp1[money.length-1]));
    }
}
Share