알고리즘 문제 풀이
프로그래머스 - 도둑질 [자바]
블린더르
2021. 2. 14. 21:17
/*
* 2021-02-14
* https://programmers.co.kr/learn/courses/30/lessons/42897?language=java
*/
package study.programmers.dynamic_programming;
public class Thievery {
public int solution(int[] money) {
// 일자로 생각하고 점화식을 만든 후
// 원형임을 고려하자
// 처음 집은 포함하지 않는 경우
int[] dp = new int[money.length];
dp[0] = 0;
dp[1] = money[1];
// 처음 집을 포함하는 경우
int[] dp2 = new int[money.length];
dp2[0] = money[0];
dp2[1] = Math.max(money[0], money[1]);
for (int i = 2; i < money.length; i++) {
dp[i] = Math.max(dp[i - 1], money[i] + dp[i - 2]);
}
for (int i = 2; i < money.length - 1; i++) {
dp2[i] = Math.max(dp2[i - 1], money[i] + dp2[i - 2]);
}
return Math.max(getLargest(dp), getLargest(dp2));
}
public int getLargest(int[] arr) {
int largest = 0;
for (int num : arr) {
if (num > largest) {
largest = num;
}
}
return largest;
}
}
점화식 생각하기 어렵다..
반응형