도둑질

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

프로그래머스

 

풀이 : 

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> money) 
{
    int answer = 0;
    // StillMoney 는 StillMoney[i]   i번째 집까지 털었을때의 최대 돈이 저장된다!!!
    vector<int> StillMoney0(money.size(), 0);
    vector<int> StillMoney1(money.size(), 0);
    
    // 첫번째 집을 털었을 경우

    StillMoney0[0] = money[0];
    StillMoney0[1] = max(money[0], money[1]);
    
    // 첫번째 집을 털면 마지막집은 털면 안되니깐 money.size() -1 까지 반복한다.
    for (size_t i = 2; i < money.size() - 1; i++)
    {
        StillMoney0[i] = max(StillMoney0[i - 1], StillMoney0[i - 2] + money[i]);
    }

    // 마지막 집을 털었을 경우
    // 첫번째 집을 건너 뛰고 2번째 집부터 위에 계산대로 계산한다.
    StillMoney1[0] = 0;
    StillMoney1[1] = money[1];

    for (size_t i = 2; i < money.size(); i++)
    {
        StillMoney1[i] = max(StillMoney1[i - 1], StillMoney1[i - 2] + money[i]);
    }

    //StillMoney0 은 size의 -1 까지 반복했기때문에 size만큼 생성한 배열에서 1개가 덜채워져 있다.
    answer = max(StillMoney0[StillMoney0.size() - 2], StillMoney1.back());

    return answer;
}

 

 

코드 설명 : 

1.  DP 배열 초기화 :
   
   • 동적 프로그래밍 배열(기억하며 풀기)을 활용하여 풀이해야한다.
   • StillMoney0 과 StillMoney1 배열을 각각 만들고 0번째집을 털었을때, 0번째를 털지않고 마지막집을 털었을때로 정의한다.
   • StillMoney[i] 라고 하면 i번째 집까지 털었을때 훔친돈의 최대값을 의미한다.
2. DP배열 업데이트 
   • 각 StillMoney0 과 StillMoney1은 이전 집까지의 최댓값과 그 전전 집까지의 최대값에 현재 훔치려는 집의 돈을 더한 값 중 더 큰값으로 업데이트 됩니다.
3. 최종 결과 계산 :
   • StillMoney0과1에 마지막에 할당한 숫자를 비교하여 더 큰곳이 최대값을 가집니다.