Programmers - 도둑질 with JAVA

 

문제

문제는 다음과 같다.

집마다 가지고 있는 돈이 정해져있고 도둑은 집을 털어서 최대한 많은 돈을 훔치려고 한다.

이 때, 인접해있는 집은 털 수 없으며, 집의 구조는 원의 형태를 갖고 있다.

[1, 2, 3, 1] 이 있을 때, 인덱스 0을 털면 마지막 인덱스는 털 수 없다.

 

 

로직

기본적으로 이런 DP 문제의 해결방법은 간단하다.

dp[0] = 인덱스 0까지 존재한다고 했을 때 털 수 있는 돈의 최대치

dp[1] = 인덱스 0~1까지 존재한다고 했을 때 털 수 있는 돈의 최대치

dp[2] = 인덱스 0~2까지 존재한다고 했을 때 털 수 있는 돈의 최대치

...

 

하지만 이 문제는 좀 다르다

집의 구조가 원형이기에 처음인덱스를 털면 마지막인덱스를 털 수 없게 된다.

 

해결방법은 두개의 리스트를 만들어 값을 구하고 그 결과의 최대값을 구한다

예를 들어, [1, 2, 3, 4, 5, 6] 인덱스가 있다.

[1, 2, 3, 4, 5], [2, 3, 4, 5, 6] 으로 나누어 각각의 리스트에 위의 로직을 적용하고 각 최대값들의 최대값이 정답이 되는 것이다.

 

 

코드

import java.util.*;
class Solution {
    public int solution(int[] money) {
        int answer = 0;
        int length = money.length;
        int[] check1 = Arrays.copyOfRange(money, 1, length);
        int[] check2 = Arrays.copyOfRange(money, 0, length-1);
        int[][] check = {check1, check2};
        for(int[] now : check){
            int[] dp = new int[length-1];
            dp[0] = now[0];
            dp[1] = Math.max(dp[0], now[1]);
            for(int i=2; i<length-1; i++){
                dp[i] = Math.max(dp[i-2]+now[i], dp[i-1]);
            }
            answer = Math.max(dp[length-2], answer);
        }
        return answer;
    }
}

 

 

import java.util.*;
class Solution {
    public int solution(int[] money) {
        int[] dp1 = new int[money.length-1];
        dp1[0] = money[0];
        dp1[1] = Math.max(money[1], dp1[0]);
        for(int i=2; i<money.length-1; i++){
            dp1[i] = Math.max(dp1[i-2]+money[i], dp1[i-1]);
        }
        int[] dp2 = new int[money.length-1];
        dp2[0] = money[1];
        dp2[1] = Math.max(money[2], dp2[0]);
        for(int i=2; i<money.length-1; i++){
            dp2[i] = Math.max(dp2[i-2]+money[i+1], dp2[i-1]);
        }
        int answer = 0;
        for(int i : dp1){
            answer = Math.max(i, answer);
        }
        for(int i : dp2){
            answer = Math.max(i, answer);
        }
        return answer;
    }
}