[프로그래머스][DP][C++] 도둑질

문제

프로그래머스 DP - 도둑질 (Level 4)

코딩테스트 연습 - 도둑질

 

---

문제 풀이

접근 방식

도둑이 훔칠 수 있는 돈의 최댓값을 구하는 문제이다.

주어진 집들은 원형으로 배치되어 있고,  인접한 집을 털 수 없다는 점을 고려하여 문제를 해결하였다.

 

우선, 집이 3개만 있을 때에는 한 집만 선택 가능하기 때문에, 3군데 중 최댓값을 리턴해주었다.

그 이상인 경우에는 DP 방법으로 문제를 해결하였다.

즉, 첫 번째 집을 반드시 포함하는 경우의 최댓값을 DP1, 두 번째 집을 포함하는 경우를 DP2,

세 번째 집을 포함하는 경우를 DP3에 각각 저장하였고, 이를 활용하여 답을 구해주었다.

 

DP에는 이전 지점에서의 최댓값과 현재 지점에서의 최댓값을 저장할 수 있도록 구현하였다.

즉, 처음에는 각 첫 집의 money 값으로 초기화해주었고,

DP[0] + money[i+2]의 값과 DP[1]의 값을 비교하여 더 큰 값을 DP[1]에 저장해주는 방식으로 최댓값을 구하였다.

마지막으로 DP1[1]과 DP2[1], DP3[1] 중 최댓값을 최종적인 답으로 리턴해주었다.

 

---

풀이 코드 - C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> money) {
    int DP1[2] = {money[0], money[0]};  // 1st 반드시 포함
    int DP2[2] = {money[1], money[1]};  // 2nd 반드시 포함
    int DP3[2] = {money[2], money[2]};  // 3rd 반드시 포함
    
    int len = money.size();
    if(len == 3)
        return *max_element(money.begin(), money.end());
    
    for(int i = 0; i < len - 3; i++){
        if(DP1[0] + money[i+2] > DP1[1]){
            DP1[0] += money[i+2];
            swap(DP1[0], DP1[1]);
        }
        else
            DP1[0] = DP1[1];
    }
    
    for(int i = 1; i < len - 2; i++){
        if(DP2[0] + money[i+2] > DP2[1]){
            DP2[0] += money[i+2];
            swap(DP2[0], DP2[1]);
        }
        else
            DP2[0] = DP2[1];
    }
    
    for(int i = 2; i < len - 2; i++){
        if(DP3[0] + money[i+2] > DP3[1]){
            DP3[0] += money[i+2];
            swap(DP3[0], DP3[1]);
        }
        else
            DP3[0] = DP3[1];
    }
    
    vector<int> answer;
    answer.push_back(DP1[1]);
    answer.push_back(DP2[1]);
    answer.push_back(DP3[1]);
    return *max_element(answer.begin(), answer.end());
}

실행 결과

실행 결과 : 100.0