도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.
각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.
제한사항
이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.
입출력 예
[간단설명] 도둑이 연속된 집이 아닌 돈을 훔칠 때, 돈의 최대값 구하기
[접근방법] 1. 첫번째 집을 포함하는 경우, 배열을 만들고 값을 초기화 한다. 2. 마지막 집을 포함하는 경우, 배열을 만들고 값을 초기화 한다. 3. 각각 (2번째전 + 현재위치), (이전위치) 값의 최대값을 현재위치에 저장한다. ㄴ> 동적계획법(Dynamic Programming) 4. 두 배열중 더 큰 숫자를 리턴한다.
[주의사항] 배열을 초기화 할때, 0번째 인덱스 값에 0을 넣어주자. ㄴ> 1번째, 2번째 값을 DP 점화식으로 비교해야하기 때문에
[소스공개]
class Solution {
public int solution(int[] money) {
// 처음 집이 포함일때
int[] first = new int[money.length+1];
// 마지막 집이 포함일때
int[] last = new int[money.length+1];
// 0번째 배열에 0을 넣어준다
// dp 점화식에 0이 없으면, 1번째, 2번째 숫자를 비교할 수 없다
first[0]=0;
last[0]=0;
// 1번째 배열부터 값을 넣어준다
// first : money 마지막값 제외
// last : money 처음값 제외
for(int i=0;i<money.length-1;i++){
first[i+1]=money[i];
last[i+1]=money[i+1];
}
// 2번째 배열부터 max 값찾기
// 1) 2번째 전 위치 값 + 현재 위치 값
// 2) 직전 위치 값
// 처음 집 포함일 경우, 마지막 집 포함일 경우 둘다 계산
for(int i=2;i<first.length;i++){
first[i]=Math.max(first[i-2]+first[i], first[i-1]);
last[i]=Math.max(last[i-2]+last[i], last[i-1]);
}
// 처음 집, 마지막 집 결과중 최대값 리턴
return Math.max(first[money.length],last[money.length]);
}
}
