도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.
각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.
제한사항
이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.
📎 예시
money
return
[1, 2, 3, 1]
4
✍🏻 풀이 방법
동적 계획법을 이용해서 풀어야 하는 문제였다.
두 가지의 경우를 생각해서 풀기로 했다.
첫 번째는, 첫 집을 털고 마지막 집을 털지 않는 경우이다.
두 번째는, 첫 집을 털지 않고 마지막 집을 터는 경우이다.
첫 집과 마지막 집은 옆집이기 때문에 두 가지 경우로 나누어서 풀기로 했다.
두 개의 int 배열을 선언해 주었다.
public int solution(int[] money) {
int len = money.length;
int[] dp1 = new int[len]; // 첫 집을 털고, 마지막 집을 털지 않는 경우
int[] dp2 = new int[len]; // 첫. 집을 털지 않고, 마지막 집을 터는 경우
}
첫 번째 배열은 첫 집을 털고, 마지막 집을 털지 않는 경우이다.
그래서 0번째 인덱스와 1번째 인덱스에 money의 0번째 인덱스 값을 넣어주었다.
두 번째 배열은 첫 집을 털지 않고, 마지막 집을 터는 경우이다.
그러면 두 번째 집부터 털게 되므로, 0번째 인덱스에는 0을 1번째 인덱스에는 money의 1번째 값을 넣어 주었다.
public int solution(int[] money) {
..
dp1[0] = money[0];
dp1[1] = money[0];
dp2[0] = 0;
dp2[1] = money[1];
}
반복문을 돌며, 각 배열에 값을 넣어주었다.
최대로 털 수 있는 값을 구하기 때문에 Math.max를 이용해 큰 값들을 넣어주었다.
첫 번째 배열은 마지막 집을 털지 않기 때문에 money의 길이에서 -2의 값을, 두 번째 배열은 마지막 집을 털기 때문에 money의 길이에서 -1한 값을 비교해주었다.
두 값 중 더 큰 값을 리턴시켜주었다.
public int solution(int[] money) {
..
for (int i = 2; i < len; i++) {
dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + money[i]);
dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + money[i]);
}
return Math.max(dp1[len - 2], dp2[len - 1]);
}
✍🏻 최종 풀이
public int solution(int[] money) {
int len = money.length;
int[] dp1 = new int[len];
int[] dp2 = new int[len];
dp1[0] = money[0];
dp1[1] = money[0];
dp2[0] = 0;
dp2[1] = money[1];
for (int i = 2; i < len; i++) {
dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + money[i]);
dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + money[i]);
}
return Math.max(dp1[len - 2], dp2[len - 1]);
}
댓글