프로그래머스 Lv4 도둑질 Java

문제설명

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

구현방법

• 처음 생각한 방법은 각 집이 원형이 아닌 1자로 놓여져 있는 상태 였다. 하지만 이 상태에서 원형으로 이어지는 상태를 판별하려니 어려움이 있었다.

• 첫번째 집을 무조건 선택한 경우와 선택하지 않은 두가지 경우로 나누어 풀면 간단하게 해결할 수 있다.

코드

class Solution {
    public int solution(int[] money) {
        int n = money.length;
        int dp[] =  new int[n];
        dp[0] = 0;
        dp[1] = 0;
        for(int i=2;i<money.length-1;i++){
            dp[i] = Math.max(dp[i-1],money[i]+dp[i-2]);
        }
        int dp2[] = new int[n];
        dp2[0] = 0;
        dp2[1] = money[1];
        for(int i=2;i<money.length;i++){
            dp2[i] = Math.max(dp2[i-1],money[i]+dp2[i-2]);
        }
        return Math.max(dp[n-2]+money[0],dp2[n-1]);
    }
}