[level 4] 도둑질 - 42897

문제 링크

성능 요약

메모리: 101 MB, 시간: 32.53 ms

구분

코딩테스트 연습 > 동적계획법（Dynamic Programming）

채점결과

정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0

제출 일자

2024년 10월 03일 21:28:58

문제 설명

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

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

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

제한사항

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

입출력 예

money	return
[1, 2, 3, 1]	4

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

---

풀이

• DP를 0번 집을 훔치는 경우와 안 훔치는 경우로 나눠서 누적합 계산한다.
  n-1번 집을 훔치려면 0번 집을 훔치지 않았어야 경보가 울리지 않는다.
• 훔칠때 점화식:
  $f(n)=Max(f(n-1),f(n-2)+money[n],f(n-3)+money[n])$
  으로 3가지 경우로 나눠서 갱신한다.

---

코드

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

		int[] dp1 = new int[n]; // 0번 집 훔침
		int[] dp2 = new int[n]; // 0번 집 안 훔침

		dp1[0] = money[0];
		dp1[1] = dp1[0];
		dp1[2] = dp1[0] + money[2];

		dp2[0] = 0;
		dp2[1] = money[1];
		dp2[2] = Math.max(money[1], money[2]);

		steal(dp1, money);
		steal(dp2, money);

		// dp1의 경우 n-1번 집을 훔칠 수 없으므로 n-2번째와 비교
		int result = Math.max(dp1[n - 2], dp2[n - 1]);

		return result;
	}

	public static void steal(int[] dp, int[] money) {
		int n = money.length;

		for (int i = 3; i < n; i++) {
			int a = dp[i - 1];
			int b = dp[i - 2] + money[i];
			int c = dp[i - 3] + money[i];

			if (a > b) {
				if (a > c) {
					dp[i] = a; // a > b, a > c
				} else {
					dp[i] = c; // c > a > b
				}
			} else {
				if (b > c) {
					dp[i] = b; // b > a, b > c
				} else {
					dp[i] = c; // c > b > a
				}
			}
		}
	}
}