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;
    }
}

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;
    }
}

다른 사람의 풀이를 참고하여 코드를 훨씬 간결하게 수정하였다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges