[1일 1알고] 도둑질

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

프로그래머스

오늘은 간단한 문제입니다.

 

가장 일반적인 dp문제를 아주 쪼끔 비틀었는데요

 

dp[i] = max(dp[i-1], dp[i-2] + val); 로 이루어지는 점화식을 활용합니다.

 

원형으로 이루어져있기 때문에 끝과 끝이 만나는 지점의 처리방법만 생각하면 됩니다.

 

간단하게 첫 집을 고르는 경우와 고르지 않는 경우를 나눠 계산한다면 마지막 집을 선택할 수 있는 가능성이 있는것, 없는 것으로 나누어지고 이에 따라 dp를 계산하면 정답이 나오게 됩니다.

 

#include <string>
#include <vector>

using namespace std;
int GetResult(const vector<int>& money, int start, int end)
{
    int prev2 = 0;
    int prev1 = 0;

    for (int i = start; i <= end; ++i)
    {
        int cur = max(prev1, prev2 + money[i]);
        prev2 = prev1;
        prev1 = cur;
    }

    return prev1;
}


int solution(vector<int> money) {
    int answer = 0;
    int N = money.size();

    int case1 = GetResult(money, 0, N - 2);
    int case2 = GetResult(money, 1, N - 1);

    return max(case1, case2);
}