[프로그래머스] 도둑질

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(vector<int> money) {
    int n = money.size();
    
    vector<int> dpFirst(n, 0);
    dpFirst[0] = money[0];
    dpFirst[1] = max(money[0], money[1]);
    
    for (int i = 2; i < n - 1; ++i) {
        dpFirst[i] = max(dpFirst[i-1], dpFirst[i-2] + money[i]);
    }
    
    vector<int> dpLast(n, 0);
    dpLast[1] = money[1];
    dpLast[2] = max(money[1], money[2]);
    
    for (int i = 3; i < n; ++i) {
        dpLast[i] = max(dpLast[i-1], dpLast[i-2] + money[i]);
    }
    
    return max(dpFirst[n-2], dpLast[n-1]);
}

---

📝 풀이

원형 배열이고 인접한 두 집은 털 수 없으니 첫 번째 집을 털었을 경우와 털지 않았을 경우로 나누어야 합니다.

첫 번째 집을 턴 경우는 마지막 집을 털 수 없으므로 money[0]부터 money[n-2]까지의 범위입니다.

첫 번재 집을 털지 않은 경우는 마지막 집을 털 수 있으므로 money[1]부터 money[n-1]까지의 범위입니다.

 

각 배열의 dp[i]는 i번째 집까지 훔칠 수 있는 최대 금액입니다.

i번째 집을 털지 않은 경우 👉 dp[i-1]

i번째 집을 털 경우 👉 dp[i-2] + money[i]

둘 중 큰 값을 선택하여 dp[i]를 갱신합니다.

 

최종적으로 두 경우 중 큰 값을 return 합니다.