[프로그래머스 Lv4][자바] 도둑질

❓문제설명

 

도둑질

프로그래머스

---

🔍문제해석

어떤걸 풀어야 할까?

• 이렇게 원형으로 집들이 배치되어있을때, 도둑이 집을 털어 가장 많이 훔칠 수 있는 돈을 구하라.
• 단, 각 집들은 인접한 집들과 방범장치가 연결되어있기 때문에 두 집을 연달아서 털게 되면 경보가 울린다.

---

🧐문제풀이

• 문제 풀이 구상

https://school.programmers.co.kr/questions/12213

 

위 게시글의 힌트를 얻어 풀이를 생각해보았다.

원형으로 구성되어있는데 인접한 두 집은 털지 못하니, 

1. 첫번째 집을 털고 마지막 집은 털지 않았을때

2. 첫번째 집을 털지않고 마지막 집은 털었을때 

위 2개의 케이스에 대해서 dp를 적용하고, 두 개의 결과값 중 가장 큰 값을 정답으로 리턴한다.

 

• 알고리즘 선택

인접한 두 집을 털지 못한다는 건 현재 집을 털던지 아니면 그냥 가는지 두 개의 케이스를 계속 비교하여 더 큰 수를 계산해야 한다는 것이다.

결국 이전의 계산된 결과를 갖다 쓴다는 점에서 DP, 동적계획법을 선택했다.

---

！제출코드

1. 첫번째 케이스 계산 
2. 첫 번째 집을 털고, 마지막 집을 털지 않는 경우 시작 => 1번 계산 시, 각 집까지 들렀을때 가장 많이 훔칠 수 있는 금액 담는 배열 생성
3. 첫번째 집에서 훔친 돈을 첫번째 인덱스에 대입
4. 첫번째 집만 털거나, 첫번째 집을 털지 않고 두번째 집을 털었을 때의 경우 중 더 큰 금액 대입
5. 마지막 집은 제외하고 반복문 시작
6. 해당 집을 털지 않거나, 터는 경우 중 더 큰 금액을 대입한다.
7. 마지막 집 계산 
8. 두번째 케이스 계산,첫 번째 집을 털지 않고, 마지막 집을 터는 경우 시작 => 2번 계산 시, 각 집까지 들렀을때 가장 많이 훔칠 수 있는 금액 담는 배열 생성
9. 두번째 집에서 훔친 돈을 두번째 인덱스에 대입
10. 두번째 집만 털거나, 두번째 집을 털지 않고 세번째 집을 털었을 때의 경우 중 더 큰 금액 대입
11. 마지막 집 까지 포함하고 반복문 시작
12. 두 케이스 중 더 큰 값 리턴

import java.util.*;

class Solution {

    public static int solution(int[] money) {
    
        int n = money.length;

        // (1) 첫 번째 집을 털고 마지막 집을 털지 않는 경우
        // (2) 해당 집까지 털었을때 가장 많은 금액을 담는 배열
        int[] dp1  = new int[n]; 
        
        // (3)
        dp1[0] = money[0];
        // (4) 첫번째 집만 털거나, 첫번째 집을 털지 않고 두번째 집만 털었을때의 가장 큰 금액
        dp1[1] = Math.max(money[0], money[1]);  

        // (5) 마지막 집은 털지 않기 때문에 제외
        for (int i = 2; i < n -1 ; i++) { 
            // (6) 털지 않고 직전 금액 계승, 지지난 금액 + 현재 금액 더하면서 턴다.
            dp1[i] = Math.max(dp1[i-1], dp1[i-2] + money[i]); 
        }
        
        // (7) 마지막 집은 털지 않고, 지지난 집의 최대금액 계승
        dp1[n-1] = dp1[n-2]; 

        // (8)첫번째 집을 털지 않고 두번째 집을 터는 경우
        int[] dp2 = new int[n];
        // (9)
        dp2[1] = money[1];
        // (10) 두번째 집만 털거나, 두번째 집을 털지 않고 세번째 집만 털었을때의 가장 큰 금액
        dp2[2] = Math.max(money[1], money[2]);  

        // (11)
        for (int i = 3; i < n ; i++) {
            dp2[i] = Math.max(dp2[i-1], dp2[i-2] + money[i]);
        }

        // (12) 두 개의 케이스 중 더 큰 값 리턴
        return Math.max(dp1[n-1], dp2[n-1]);
    }
}