<프로그래머스> 도둑질

<링크>

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

프로그래머스

 

 

<문제>

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

• 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
• 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

<제한사항>

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

<입력 및 출력>

money	return
[1, 2, 3, 1]	4

 

<아이디어>

1. 마을이 짝수개인지 홀수개인지에 따라서 털었던 값을 저장할 배열을 각각 만들어야겠네..
2. 첫값을 초기화 할때첫째집을 터는 경우랑, 첫째집 패스하고 둘째집을 터는 경우로 또 나눠서 시작해야지..
3. 첫째집을 안털고, 마지막 집을 털수 있는 경우만 따지면 모든 경우 다 따지는거.. 맞겠지...?
4. 정리하면 
   1. 첫째 집 털고, 마지막집 못텀 (무조건 못털어요 마지막집은. 붙어있잖아 원형으로 둘러쌓여있어서)
   2. 첫째 집 털수 있지만, 둘째 집부터 털고, 마지막집 못텀
   3. 둘째 집털고, 마지막 집 털기 
5. 도둑질은 하지말자.

<풀이 - Java >

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

        // 첫번째 집을 털수 있고, 마지막 집은 털지 않는 경우
        int[] dpFirst = new int[n];
        // 첫 집 저장
        dpFirst[0] = money[0];
        // 첫집이랑 두번째 집 비교를 해보아요
        dpFirst[1] = Math.max(money[0], money[1]);
        for (int i = 2; i < n - 1; i++) {
            // 내 DP 값은, 이전 값이랑 전전값이랑 현재위치의 money값을 더한값중 큰거를 넣겠어..
            dpFirst[i] = Math.max(dpFirst[i - 1], dpFirst[i - 2] + money[i]);
        }
        
        // 첫 번째 집을 털지 않고 마지막 집을 털 수 있는 경우
        int[] dpSecond = new int[n];
        // 못털어요 ㅠ
        dpSecond[0] = 0;
        // 대신 두번째 집은 털겠어요.
        dpSecond[1] = money[1];
        for (int i = 2; i < n; i++) {
            // 내 DP 값은, 이전 값이랑 전전값이랑 현재위치의 money값을 더한값중 큰거를 넣겠어..
            // dpSecond[2] = dpSecond[1] 이랑, dpSecond[0] + money[2] 중 큰거를 저장하겠어..
            dpSecond[i] = Math.max(dpSecond[i - 1], dpSecond[i - 2] + money[i]);
        }
        // dpFirst는 마지막 집을 못털어. 마지막집의 위치가 n-1번째니까, n-2 위치가 가장 큰값이겠군
        // dpSecond는 마지막집을 털어. 마지막 집의 위치가 n-1번째니까, n-1 위치가 가장 큰값이겠지?
        answer = Math.max(dpFirst[n-2] , dpSecond[n-1]);
        return answer;
        
    }
}