> 문제
문제 : [도둑질]
문제풀이
DP를 활용하여 인접한 집은 계산할 수 없기 때문에, dp[index - 2] + money[index] 와 dp[index–1]을 비교하여 최댓값을 계속 갱신해 주었다.
문제는 파라미터로 주어지는 집의 배열이 원형의 조건을 가지고 있기 때문에, 첫번째 집이 포함된다면, 마지막 집은 포함되면 안된다. 반대로 첫번째 집이 포함되지 않는다면, 마지막 집은 포함될 수 있다.
소스는 다음과 같다.
class Solution {
public int solution(int[] money) {
int[] dp = new int[money.length];
// 첫번째 집이 포함될 경우.
dp[0] = money[0];
dp[1] = money[0];
int max = dp[0];
for(int i=2; i<money.length - 1; i++){
dp[i] = Math.max(dp[i-2] + money[i], dp[i-1]);
max = Math.max(max, dp[i]);
}
// 첫번째 집이 포함되지 않을 경우.
dp[0] = 0;
dp[1] = money[1];
for(int i=2; i<money.length; i++){
dp[i] = Math.max(dp[i-2] + money[i], dp[i-1]);
max = Math.max(max, dp[i]);
}
return max;
}
}
문제 출처 : Programmers