[프로그래머스 | Java Lv.4] 도둑질 (DP, 동적 프로그래밍)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42897

프로그래머스

 

어렵다 어려워

---

접근

 

- 인접해 있는 집을 털면 안됨

- 최대로 많이 털어야 함

 

집이 원형으로 있다 보니, 첫 집을 터는 경우와 털지 않을 경우 2가지를 고려해야 했던 문제

 

점화식

 dp 배열을 만들어서 점수를 기억하게 하면 점화식은

 

현재 i번째 dp 점수 = Math.max(현재 집을 털 경우(현재 집 점수 + i-2번째 dp 점수), 털지 않을 경우(i-1번째 dp 점수)) 

dp[i] = Math.max(money[i]+dp[i-2], dp[i-1]);

 

첫번째 제출 - 테스트케이스 1번 실패

package week5.baek.dp;

public class Ex5 {
    public static int solution(int[] money) {
        //첫번째 집을 터는 경우
        int[] dp1 = new int[money.length];
       //첫번째 집을 털지 않는 경우
        int[] dp2 = new int[money.length];

       dp1[0] = money[0];
       dp1[1] = money[1];

       dp2[0] = 0;
       dp2[1] = money[1];

        for (int i = 2; i < money.length; i++) {
            if (i == money.length - 1) {
                dp1[i] = dp1[i - 1];
                dp2[i] = money[i] + dp2[i - 2];
            } else {
                dp1[i] = Math.max(money[i] + dp1[i - 2], dp1[i - 1]);
                dp2[i] = Math.max(money[i] + dp2[i - 2], dp2[i - 1]);
            }
        }


        return Math.max(dp1[money.length-2], dp2[money.length-1]);
    }

    public static void main(String[] args) {
        int[] money = {10, 5, 3, 1, 10};
        System.out.println(solution(money));
    }
}

https://school.programmers.co.kr/questions/9297

 

       dp1[0] = money[0];
       dp1[1] = money[1];

       dp2[0] = 0;
       dp2[1] = money[1];

 

초기화를 이렇게 해주니 통과했다 (???? 의문 알아내야함)

---

최종 코드 

package week5.baek.dp;

public class Ex5 {
    public static int solution(int[] money) {
        //첫번째 집을 터는 경우
        int[] dp1 = new int[money.length];
       //첫번째 집을 털지 않는 경우
        int[] dp2 = new int[money.length];

       dp1[0] = money[0];
       dp1[1] = money[1];

       dp2[0] = 0;
       dp2[1] = money[1];

        for (int i = 2; i < money.length; i++) {
            if (i == money.length - 1) {
                dp1[i] = dp1[i - 1];
                dp2[i] = money[i] + dp2[i - 2];
            } else {
                dp1[i] = Math.max(money[i] + dp1[i - 2], dp1[i - 1]);
                dp2[i] = Math.max(money[i] + dp2[i - 2], dp2[i - 1]);
            }
        }


        return Math.max(dp1[money.length-2], dp2[money.length-1]);
    }

    public static void main(String[] args) {
        int[] money = {10, 5, 3, 1, 10};
        System.out.println(solution(money));
    }
}

---

참고

https://born2bedeveloper.tistory.com/39#google_vignette

[프로그래머스] 도둑질-JAVA

https://yummy0102.tistory.com/676

[DP] 도둑질 - JAVA