[프로그래머스] 도둑질

도둑질

Algorithm: DP Created: Apr 06, 2020 7:47 PM DoubleChk: No Type: 프로그래머스 level: 4 link: https://programmers.co.kr/learn/courses/30/lessons/42897

문제 설명

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

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

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

제한사항

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

---

    #include <string>
    #include <vector>
    
    using namespace std;
    int dp[1000001];
    int dp2[1000001];
    int solution(vector<int> money) {
        int answer = 0;
        int ret1 = 0;
        int ret2 = 0;
        int n = money.size();
    
        //첫 번째 집 털었을 때
        dp[0] = money[0];
        dp[1] = dp[0];
        
        //첫 번째 집 안 털었을 때
        dp2[0] = 0;
        dp2[1] = money[1];
    
        for(int i=2; i<n-1; i++){
            dp[i] = max(dp[i-1], dp[i-2] + money[i]);
            ret1 = max(ret1, dp[i]);
        }
        
        for(int i=2; i<n; i++){
            dp2[i] = max(dp2[i-1], dp2[i-2] + money[i]);
            ret2 = max(ret2, dp2[i]);
        }
    
        return max(ret1, ret2);
    }

• 문제 풀이

  집이 동그랗게 되어 있기 때문에 마지막 집을 털게 되면 첫 번째 집을 털면 안된다.

  따라서 첫 번째 집을 털 경우랑 첫 번째 집을 털지 않을 경우를 구분 해 주어야 한다.

  반복문으로 현재 집을 털 경우, 안 털 경우를 계산해서 업데이트 해 준다.

  반복문이 끝나면 두 경우 중 큰 값을 return 한다.