Programmers 42897 - 도둑질

코딩테스트 연습 - 도둑질 | 프로그래머스 스쿨

프로그래머스

 

인접한 집을 털면 경보가 울린다.

그리고 집이 원형으로 배치되어 있다.

돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최대 값은?

이 두 가지 특징이 있는 상황이다.

핵심은 원형 구조이다. 따라서 1번 집이 제일 중요해진다. 1번 집을 털게 되면 마지막 집을 털 수 없게 된다. 1번 집을 털지 않는다면 마지막 집을 털 수 있게 된다.

dp [i]를 i번째 위치에서의 최댓값이라 생각해 보자. 이 값은 i-2를 털고 i를 터는 경우와 i-1을 털고 i를 안터는 경우 두 가지 중 큰 값이 될 것이다.

그런데 앞서 말했듯이 1번집부터 털지 안 털지 별개의 배열로 관리해야 한다.

import java.util.*;

class Solution {
    public int solution(int[] money) {
        int n = money.length;
        int[] dp1 = new int[n + 1];
        int[] dp2 = new int[n + 1];
        dp1[0] = money[0];
        dp1[1] = money[0];
        dp2[0] = 0;
        dp2[1] = money[1];
        
        for (int i = 2; i < n - 1; i++) {
            // 첫 집을 터는 경우
            dp1[i] = Math.max(dp1[i - 2] + money[i], dp1[i - 1]);
        }
        
        for (int i = 2; i < n; i++) {
            dp2[i] = Math.max(dp2[i - 2] + money[i], dp2[i - 1]);
        }
        
        return Math.max(dp1[n - 2], dp2[n - 1]);
    }
}