프로그래머스 도둑질 (Java)

💜 문제

---

🤔 문제 분석

집이 원형으로 배치되어 있기 때문에 첫 번째 집 위치를 정의할 수 없다.

그러므로 money 배열의 첫번째 값이 첫 번째 집이라고 두고 두 가지 상황으로 분류할 수 있다.

a. 첫번째 집을 터는 경우

b. 첫번째 집을 털지 않는 경우

이 두 경우로 분류하여 Dynamic Programming을 해보자.

---

📝 풀이

1. 테이블 정의

n번째 집을 털었을 때 총 훔친 돈의 최댓값이 들어갈 배열 정의

int[] dp_first = new int[len];    // 첫번째 집을 터는 경우
int[] dp_second = new int[len];    // 첫번째 집을 털지 않는 경우

2. 초기값 세팅

각 집에 있는 돈을 넣어준다.

for (int i = 0; i < len; i++) {
	dp_first[i] = money[i];
	dp_second[i] = money[i];
}

a. 첫번째 집을 터는 경우

첫번째 집을 터니까 두번째 집은 못 턴다.

집의 개수는 최소 3개 이므로, dp_first[2]의 초기값도 넣어준다.

dp_first[1] = -1;
dp_first[2] += dp_first[0];

b. 첫번째 집을 털지 않는 경우

첫번째 집 안 털고, 두번째집부터 털기

dp_second[0] = -1;

3. 점화식 선언

인접하지 않은 두 집(i - 2, i - 3번째 집)을 비교해 더 큰 값을 누적해 더한다.

for (int i = 3; i < len; i++) {
	dp_first[i] += Math.max(dp_first[i - 3], dp_first[i - 2]);
	dp_second[i] += Math.max(dp_second[i - 3], dp_second[i - 2]);
}

4. 결과값 도출

훔친돈의 최댓값을 구하는 것이므로,

맨 마지막 두집을 비교해 dp_first 배열과 dp_second 배열에서 최댓값을 구하고

그 둘중에서 최댓값이 answer!

여기서, dp_first는 첫번째 집을 털었으니까 맨 마지막 집은 못 턴다는 점을 고려하자.

int first_max = Math.max(dp_first[len - 2], dp_first[len - 3]);    
int second_max = Math.max(dp_second[len - 1], dp_second[len - 2]);    

answer = Math.max(first_max, second_max);

---

👀 회고

Dynamic Programming 접근 방법

1. 테이블 정의

2. 초기값 세팅

3. 점화식 선언

이 순서 기억!

---

public class 도둑질 {
	public static void main(String[] args) {
		System.out.println(solution(new int[] {1, 2, 3, 1}));
	}

	private static int solution(int[] money) {
		int answer = 0;
		int len = money.length;

		// 1. n번째 집을 털었을때 훔친 돈의 최댓값이 들어갈 배열 선언
		int[] dp_first = new int[len];    // 첫번째 집을 터는 경우
		int[] dp_second = new int[len];    // 첫번째 집을 안 터는 경우

		// 2. 배열 초기값
		for (int i = 0; i < len; i++) {
			dp_first[i] = money[i];
			dp_second[i] = money[i];
		}

		dp_first[1] = -1;    // 두번째집 안털기
		dp_second[0] = -1;    // 첫번째집 안털기
		dp_first[2] += dp_first[0];    // 집의 개수는 최소 3개이므로, dp_first[2]의 초기값도 넣어준다.

		// 3. 점화식
		for (int i = 3; i < len; i++) {
			// 인접하지 않은 집(i - 2, i - 3)과 비교해 더 큰 값을 누적해 더해줌
			dp_first[i] += Math.max(dp_first[i - 3], dp_first[i - 2]);
			dp_second[i] += Math.max(dp_second[i - 3], dp_second[i - 2]);
		}

		// 맨 마지막 두집을 비교하여 최댓값 찾기
		int first_max = Math.max(dp_first[len - 2], dp_first[len - 3]);    // 첫번째 집을 털었으니까 맨 마지막 집은 어차피 못 턴다.
		int second_max = Math.max(dp_second[len - 1], dp_second[len - 2]);    // 첫번째 집을 안 털었으니까 맨 마지막 집 털 수 있다.

		answer = Math.max(first_max, second_max);

		return answer;
	}
}