🌞문제

🌞접근법

처음 문제를 잘못 이해하고 풀었다가, 큰 낭패를 보았다. 한 집에 인접하다라는 것이 왼쪽과 오른쪽 집을 털게 될 때, 그 가운데 집에서 벨이 울리는 것으로 이해를 하고 풀다가 아무리해도 풀리지 않았다. 이 문제를 계기로 제한사항 뿐만 아니라 입력예제에 내가 예상한 값을 넣어보는 것도 중요하다는 것을 깨닫게 됐다.

이 문제의 경우에는 연속해서 두개의 집을 털게 되면, 벨이 울리게 된다.
그래서 이러한 경우 가장 많은 집을 터는 경우의 수는 홀수번 집을 털고, 짝수번 집을 터는 경우 두가지 일 것이다.

하지만 이 문제의 경우에는 각 집이 가지고 있는 money가 다르다.
그렇기 때문에 어느 경우에는 첫번째 집을 털고 두번째 세번째 집을 건너뛰고 네번째 집을 털 수도 있다는 것이다.

그렇다면 이러한 경우를 어떻게해서 찾을 수 있을까?

간단하게 생각하면 집을 하나씩 추가하면서 배열을 유지하면 될 것이라고 생각이 든다.
하나의 집만 있었을 때, 최대값은 그 집에 있는 돈일 것이다.
두개의 집만 있었을 때, 두번째 집의 돈과 첫번째 집의 돈 중에서 골라야 할 것이다.
세개의 집만 있었을 때, 첫번째 집과 세번째 집의 합 또는 두번째 집 중의 최댓값
네개의 집, 첫번째집과 세번째집, 두번째와 네번째, 첫번째와 네번째
즉 이것을 점화식으로 만든다면 네개의 집이 있는 경우를 살표보면,
두번째 집까지의 최댓값+네번째집의 값 / 세번째집까지의 최댓값 이 두가지를 비교해서 큰값을 배열에 저장을 하면 되겠다.

근데 이 문제의 경우 유의해야 할 점이 집이 원형으로 있다는 점이다.
그래서 끝에 집과 첫번째 집이 연속적으로 만나서도 안된다.

그렇기 떄문에 두가지 경우로 나누어서 생각을 해야한다.
1. 첫번째 집을 털지 않은 경우 -> 마지막 집을 털어도 된다.
2. 첫번째 집을 턴 경우 -> 마지막 집을 털어서는 안된다.

dp배열을 두개를 만들어서 최종적으로 나온 값 두개를 비교하여 큰 값이 답이된다.

🌞답

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int dp1[1000001];
int dp2[1000001];


int solution(vector<int> money) {
    dp1[0] = money[0];
    dp2[1] = money[1];
    
    for(int i=1;i<money.size()-1;i++)
    {
        if(i-2 >= 0)
        {
            dp1[i] = max(dp1[i-1],dp1[i-2]+money[i]);    
        }
        else
        {
            dp1[i] = max(dp1[i-1],money[i]);
        }
    }
    
    for(int i=2;i<money.size();i++)
    {
        if(i-1 >= 1)
        {
            dp2[i] = max(dp2[i-1],dp2[i-2]+money[i]);
        }
        else
        {
            dp2[i] = max(dp2[i-1],money[i]);
        }
    }
    
    int answer = max(dp1[money.size()-2], dp2[money.size()-1]);
    

    return answer;
}