두 번째 시도(시간 초과)
public class Solution {
// 도둑질 // 두 번째 시도(시간 초과)
public static int getMaxMoneyExceptTargetIndex(int[] money, int targetIndex) {
int[] dp = new int[money.length - 1]; // 제일 먼저 1을 뺐을 경우 2,3,1,4,2,5에서 개미전사 문제
int num1 = (targetIndex + 1) % (money.length); // 타겟 인덱스의 바로 다음 인덱스
int num2 = (targetIndex + 2) % (money.length); // 타겟 인덱스의 다음 다음 인덱스
int num3 = 0;
dp[0] = money[num1];
dp[1] = money[num2];
for (int i = 2; i < money.length - 1; i++) {
num3 = (targetIndex + i + 1) % (money.length);
dp[i] = Math.max(dp[i - 2] + money[num3], dp[i - 1]);
}
return dp[money.length - 2];
}
public static int solution(int[] money) {
int answer = 0;
int maxMoney = 0;
for (int i = 0; i < money.length; i++) {
maxMoney = Math.max(maxMoney, getMaxMoneyExceptTargetIndex(money, i)); // i번째 인덱스를 제외했을 때의 최대 값
}
answer = maxMoney;
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] money = {1, 2, 3, 1, 4, 2, 5}; // 1 빼고 2,3,1,4,2,5 개미전사 문제 // 2 빼고 3,1,4,2,5,1 개미전사 문제 // 3 빼고 1,4,2,5,1,2 개미전사 문제 // 총 7개의 값 중 max값을 return
System.out.println(solution(money));
}
}
첫 번째 시도(★ 부분으로 인해 예외 발생)
세 번째 시도 성공
public class Solution {
// 도둑질
// 첫 번째 시도(★ 부분으로 인해 예외 발생)
// 세 번째 시도 성공
public static int solution(int[] money) {
int answer = 0;
int[] dpExceptLast = new int[money.length - 1]; // 1, 2, 3, 1, 4, 2 담자
int[] dpExceptFirst = new int[money.length - 1]; // 2, 3, 1, 4, 2, 5 담자
dpExceptLast[0] = money[0]; // 1
// dpExceptLast[1] = money[1]; // 2 // ★ 첫 번째 풀이에서 예외가 발생했던 이유 !
dpExceptLast[1] = Math.max(money[0], money[1]); // 2 // 이게 맞지
dpExceptFirst[0] = money[1]; // 2
// dpExceptFirst[1] = money[2]; // 3 // ★ 첫 번째 풀이에서 예외가 발생했던 이유 !
dpExceptFirst[1] = Math.max(money[1], money[2]); // 3 // 이게 맞지
for (int i = 2; i < money.length; i++) {
if (i < money.length - 1) {
dpExceptLast[i] = Math.max(dpExceptLast[i - 2] + money[i], dpExceptLast[i - 1]);
}
if (i > 2) {
dpExceptFirst[i - 1] = Math.max(dpExceptFirst[i - 3] + money[i], dpExceptFirst[i - 2]);
}
}
answer = Math.max(dpExceptLast[money.length - 2], dpExceptFirst[money.length - 2]);
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] money = {1, 2, 3, 1, 4, 2, 5};
System.out.println(solution(money));
}
}프로그래머스 도둑질 문제 풀이 Java
'Java > 프로그래머스' 카테고리의 다른 글
| [Java] 프로그래머스 [Level-2] 두 큐 합 같게 만들기 (0) | 2022.11.27 |
|---|---|
| [Java] 프로그래머스 [Level-1] 성격 유형 검사하기 (0) | 2022.11.27 |
| [Java] 프로그래머스 [Level-4] [3차]파괴되지 않은 건물 (0) | 2022.11.27 |
| [Java] 프로그래머스 [Level-2] 주차 요금 계산 (0) | 2022.11.27 |
| [Java] 프로그래머스 [Level-3] 등대 (0) | 2022.11.27 |
