도둑질

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

코딩테스트 연습 - 도둑질 | 프로그래머스

leetcode 의 house robber 문제랑 유사 이웃하지 않은 집 노드의 합중 가장 큰 값을 출력

 

 

DP 접근

시작점은 0, 1 둘중에 하나로 시작 해야한다.

0 으로 시작 했을땐 마지막과 마주 볼수 있으니 전체크기 - 1 만큼 DP 값을 채운다.

1 로 시작했을 때는 마지막까지 DP 값을 채운다.

각각에 합중 가장 큰 값을 출력 한다.

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> money) {
    int size = money.size();
    if(size == 0)
        return 0;
    else if(size == 1)
        return money[0];

    int sol1 = money[0];
    int minus_two = 0;

    for(int i = 1; i < size - 1; ++i) {
        int tmp = sol1;
        sol1 = max(sol1, minus_two + money[i]);
        minus_two = tmp;
    }

    int sol2 = money[1];
    minus_two = 0;
    for(int i = 2; i < size; ++i) {
        int tmp = sol2;
        sol2 = max(sol2, minus_two + money[i]);
        minus_two = tmp;
    }

    return max(sol1, sol2);
}