[프로그래머스] 코딩테스트 연습 - 동적계획법(Dynamic Programming) Level 4 도둑질
Solution.java
class Solution {
public int solution(int[] money) {
int answer = 0;
if (money.length == 1) return money[0];
int[][] dp = new int[2][money.length];
dp[0] = new int[money.length];
dp[1] = new int[money.length];
dp[0][0] = money[0]; dp[0][1] = Math.max(money[0], money[1]);
dp[1][0] = 0; dp[1][1] = money[1];
for (int i = 2; i < money.length - 1; i++) {
dp[0][i] = Math.max(dp[0][i - 2] + money[i], dp[0][i - 1]);
dp[1][i] = Math.max(dp[1][i - 2] + money[i], dp[1][i - 1]);
}
dp[0][money.length - 1] = dp[0][money.length - 2];
dp[1][money.length - 1] = Math.max(dp[1][money.length - 3] + money[money.length - 1], dp[1][money.length - 2]);
answer = Math.max(dp[0][money.length - 1], dp[1][money.length - 1]);
return answer;
}
}
class Solution {
public int solution(int[] money) {
int answer = 0;
if (money.length == 1) return money[0];
int[][] dp = new int[2][money.length];
dp[0] = new int[money.length];
dp[1] = new int[money.length];
dp[0][0] = money[0]; dp[0][1] = Math.max(money[0], money[1]);
dp[1][0] = 0; dp[1][1] = money[1];
for (int i = 2; i < money.length - 1; i++) {
dp[0][i] = Math.max(dp[0][i - 2] + money[i], dp[0][i - 1]);
dp[1][i] = Math.max(dp[1][i - 2] + money[i], dp[1][i - 1]);
}
dp[0][money.length - 1] = dp[0][money.length - 2];
dp[1][money.length - 1] = Math.max(dp[1][money.length - 3] + money[money.length - 1], dp[1][money.length - 2]);
answer = Math.max(dp[0][money.length - 1], dp[1][money.length - 1]);
return answer;
}
}
DP 방식은 잘 짰었는데 처음 집과 마지막 집을 어떻게 처리할까 하다가 못 풀었다.
결국 질문하기를 보고 힌트를 얻었는데
그냥 처음 집을 넣고 마지막 집을 안 넣는 경우, 처음 집을 안 넣고 마지막 집을 넣는 경우 두 경우를 계산해서 둘 중 큰 값을 구해주면 되는거였다.
Solution.java (수정)
class Solution {
public int solution(int[] money) {
int answer = 0;
int[][] dp = new int[2][money.length];
dp[0][0] = money[0];
dp[0][1] = money[0];
dp[1][0] = 0;
dp[1][1] = money[1];
for (int i = 2; i < money.length; i++) {
dp[0][i] = Math.max(dp[0][i - 2] + money[i], dp[0][i - 1]);
dp[1][i] = Math.max(dp[1][i - 2] + money[i], dp[1][i - 1]);
}
answer = Math.max(dp[0][money.length - 2], dp[1][money.length - 1]);
return answer;
}
}
class Solution {
public int solution(int[] money) {
int answer = 0;
int[][] dp = new int[2][money.length];
dp[0][0] = money[0];
dp[0][1] = money[0];
dp[1][0] = 0;
dp[1][1] = money[1];
for (int i = 2; i < money.length; i++) {
dp[0][i] = Math.max(dp[0][i - 2] + money[i], dp[0][i - 1]);
dp[1][i] = Math.max(dp[1][i - 2] + money[i], dp[1][i - 1]);
}
answer = Math.max(dp[0][money.length - 2], dp[1][money.length - 1]);
return answer;
}
}
다른 사람의 풀이를 참고하여 코드를 훨씬 간결하게 수정하였다.
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
Author And Source
이 문제에 관하여([프로그래머스] 코딩테스트 연습 - 동적계획법(Dynamic Programming) Level 4 도둑질), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hye07on11/프로그래머스-코딩테스트-연습-동적계획법Dynamic-Programming-Level-4-도둑질저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)