[ DP ] - 도둑질(DP)

문제

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

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

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

제한사항

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

입출력 예

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

 

풀이

1. 인접한 두집을 털면 안됨, 마을은 집끼리 동그랗게 배치, 돈의 최댓값

2. 인접한 두집을 털면 안되므로 1번째 집을 털고 2번째 집을 안털고를 반복하는 방법, 1번째 집을 안털고 2번째 집을 털고를 반복하는 방법

3. 1번째 집을 터는 방법은 1번째 집을 털었으니 money[0]를 대입하고, 2번째집은 1번째 집 털었으니 1번째집 턴 그대로의 값 유지

4. 2번째 집을 터는 방법은 1번째집을 0으로 처리하고 2번째 집을 털었으니 money[1]를 대입 처리

5. 2번째 이후의 집을 터는 방식의 점화식은 전전(i-2) 집과 전(i-1) 집 중 max 값을 해당 턴 값으로 처리

6. money 배열 길이만큼 반복 후 터는 방식 때문에 마지막-1, 마지막 인덱스에 젤 큰 값이 저장된다. 그러므로 마지막 인덱스의 두개의 값을 max로 비교하여 return

 

코드

public class Theif {
	public static void main(String[] args) {
		int[] money = {1, 2, 3, 1};
		solution(money);
	}
	public static void solution(int[] money) {
		// 첫번째 집 터는 방
		int[] firstHouse = new int[money.length];
		// 두번째 집 터는 방
		int[] secondsHouse = new int[money.length];
		
		// 첫번째 집 털경우 0에 털었으니 돈[0]값
		// 두번째 집은 첫번째집 털었으니 못털고 지나치므로 첫번째집값그대
		firstHouse[0] = money[0];
		firstHouse[1] = money[0];
		// 두번째 집 털경우 첫번재집은 돈 0처리
		// 털었으니 두번째 집에 돈[1]값
		secondsHouse[0] = 0;
		secondsHouse[1] = money[1];
		
		// 두번째 이후의 집 처리하는 점화식
		// money[i]+[i-2],[i-1] 의 전전집, 전집 중 max값 비교하여
		// for문 돌때마다 한칸씩 비교하므로 마지막 인덱스(마지막-1,마지막)엔 젤 큰값이 저장된다.
		for(int i=2; i<money.length; i++) {
			firstHouse[i] = Math.max(firstHouse[i-1], money[i]+firstHouse[i-2]);
			secondsHouse[i] = Math.max(secondsHouse[i-1], money[i]+secondsHouse[i-2]);
		}
		System.out.println(Math.max(firstHouse[money.length-2], secondsHouse[money.length-1]));
		
	}
}