[프로그래머스] 도둑질

문제

---

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

 

 

 

풀이

---

https://conpulake.tistory.com/163?category=841398 

[프로그래머스] 스티커 모으기(2)

위 문제와 풀이가 동일하다.

 

동적계획법을 이용하여, 현재의 집까지의 도둑질한 돈의 최대값을 저장하면 된다.

원형이기 때문에 처음집을 도둑질하면 마지막집은 도둑질하면 안된다.

반대로 마지막집을 도둑질하면 처음집은 도둑질하면 안되기 때문에, 두가지의 경우를 저장할 테이블을 두개 선언한 뒤에 풀면 된다.

 

첫번째 집을 도둑질 한경우는 money.length - 2 부분을 봐주어야한다. (마지막 집을 도둑질 한 경우는 제외하기 위해)

첫번째 집을 도둑질 하지 않은 경우는 money.length - 1 부분을 봐주면 된다.( 마지막 집을 도둑질 할 수 있는 경우기 때문이다.)

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