도둑질

문제

프로그래머스

n개의 집이 있으면 각각 돈이 있다. 서로 이웃하지 않는 선에서 돈을 훔칠 때 가장 최댓값을 구하라.

단순히 생각하면 dp[i] = Math.max(dp[i-1], dp[i-2] + money[i]) 라고 점화식을 세울 수 있다.

하지만 집이 원형으로 이뤄져 있다는 점에서 다르게 생각해 주어야 한다.

 

즉, 첫번째 집을 선택하면 맨 마지막 집을 선택할 수 없습니다.

반대로 첫번째 집을 선택하지 않고 두번째 집을 선택하면 마지막 집까지 선택할 수 있습니다.

이를 dp 식으로 표현하면 아래와 같다.

class Solution {
    public int solution(int[] money) {
        int answer = 0;

        int []dp = new int[money.length];
        
        //첫번째 집을 고르고 마지막 집을 고르지 않는다.
        dp[0] = money[0]; //첫번째 집 선택
        dp[1] = money[0]; //두번째 집은 선택하지 않으므로 첫번째 집의 돈 넣어줌
        
        for(int i=2;i<money.length-1;i++){ //마지막 집은 선택하면 안되므로 money.length-1까지 탐색
            dp[i] = Math.max(dp[i-1], dp[i-2] + money[i]);
        }
        answer = dp[money.length-2]; //첫번째 집 선택하고 돌렸을 때 최댓값
        
        //첫번째 집을 고르지 않는다. 
        dp[0] = 0; //첫번째 집은 안고름
        dp[1] = money[1]; //두번째 집은 고름
        for(int i=2;i<money.length;i++){ //마지막 집까지 탐색
            dp[i] = Math.max(dp[i-1], dp[i-2] + money[i]);
        }
        
        answer = Math.max(answer, dp[money.length-1]); //첫번째 집 선택 최댓값과 비교해서 정답 도출
        return answer;
    }
}