프로그래머스_도둑질(JAVA)

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

프로그래머스

[문제 풀이]

DP(Dynamic Programming)를 이용하여 문제를 풀었습니다.

 

도둑질 문제는 주어진 집 배열에서 인접한 두 집을 연속해서 털지 않고 훔칠 수 있는 최댓값을 구하는 문제입니다.

주어진 문제는 두 집을 연속해서 털 수 없기 때문에 첫번째 집을 터는 경우와 털지 않을 경우를 나눠야 합니다. 각각의 경우에 대해서 DP 배열에 메모라이징합니다.

 

구현방법은 아래와 같습니다.

1. 집 배열 크기의 DP배열을 생성 합니다.
2. 첫번째 집을 터는 경우를 초기화합니다.
3. 이 경우 마지막 집과 두번째 집은 털 수 없습니다.
   
4. 점화식은 아래와 같으며, 마지막 집 앞에까지 배열을 순회합니다.
   dp1[i-1], dp1[i-2]+money[i]
   
5. 첫번째 집을 털지 않는 경우를 초기화합니다.
6. 이 경우 첫번째 DP 배열의 값은 0입니다.
7. 점화식은 아래와 같으며, 마지막 집까지 배열을 순회합니다.
   dp2[i-1], dp2[i-2]+money[i]
   
8. dp1은 마지막 집을 털 수 없으므로 dp1[n-2], dp2[n-1] 값을 비교합니다.

[JAVA]

public class Solution {
    public int solution(int[] money) {
        int n = money.length;
        int[] dp1 = new int[n]; //첫 번째 집을 털었을 때
        int[] dp2 = new int[n]; //첫 번째 집을 털지 않았을 때
        
        dp1[0] = money[0];
        dp1[1] = money[0];
        for (int i = 2; i < n-1; i++) {
            dp1[i] = Math.max(dp1[i-1], dp1[i-2]+money[i]);
        }
        
        // 첫 번째 집을 털지 않고 시작하는 경우
        dp2[0] = 0; // 첫 번째 집을 털지 않으므로 첫 번째 집의 돈은 없음
        dp2[1] = money[1];
        for (int i = 2; i < n; i++) {
            dp2[i] = Math.max(dp2[i-1], dp2[i-2]+money[i]);
        }
        
        return Math.max(dp1[n-2], dp2[n-1]);
    }
}