[프로그래머스] 도둑질 - JAVA

프로그래머스 코딩 테스트 연습 문제 -  도둑질  / JAVA 풀이 정리

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

프로그래머스

---

풀이 방법

이 문제는 동적 계획법(Bottom-Up)을 사용해 풀이하는데, 최대한 많은 돈을 훔치며 도둑질하기라는 전체 문제를

 

1. 도둑질을 첫 번째 집부터 시작하기
2. 도둑질을 두번째 집부터 시작하기

두 가지의 부분 문제로 나누어 해결한다.

---

코드 풀이

▶ 첫번째 집을 터는 경우

// 첫번째 집을 털 경우
        dp1[0] = money[0];
        dp1[1] = money[0];
	// n은 집의 갯수
        for (int i = 2; i < n - 1; i++) {
            dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + money[i]);
        }

첫번째 집을 터는 경우에 맞게 배열을 초기화한다.

현재(i번째) 집을 털었을 때의 최대 금액을 계산하기 위해 아래 값을 비교해 최대값을 dp1[i]에 저장한다.

• dp1[i - 1] : 이전 집을 털었을 때의 값
• dp1[i - 2] + money[i] : (이번 집을 털기 위해) 전전집을 턴 경우의 최대 금액 + 이번 집에 있는 money 값

※ (n - 1) 까지만 반복하는 이유 → 첫번째 집을 터는 경우이기 때문에 마지막 집은 털 수 없음

---

▶ 두번째 집을 터는 경우(첫 번째 집을 털지 않는 경우)

// 첫번째 집을 털지 않는 경우
        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]);
        }

첫번째 집을 털지 않았으니까 dp2[0] = 0 으로 초기화한다.

나머지는 위 경우와 동일하게 반복문을 통해 최대 금액을 계산하는데,

첫번째 집을 털지 않아 마지막 집을 털 수 있으므로 n까지 반복하면 된다.

 

	// 두 결과 중 최대값을 선택해 반환
        return Math.max(dp1[n - 2], dp2[n - 1]);

각 경우에 따라 털 수 있는 마지막 집까지 계산을 끝낸 값을 비교해 최대 금액을 선택해 return한다.

---

전체 코드

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]);
    }