[프로그래머스] 도둑질 (C/C++)

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

첫번째로 생각해야 할 것은 첫번째 집을 털었냐 이다.

원형이기 때문에 마지막집과 첫번째집이 붙어있기 때문이다.

 

그래서 cache를 2차원배열로 1000000 x 2로 선언해주었다.

 

어떤 index의 집에 도착했을 때 이집을 털거나 안털거나로 두가지 선택이 존재한다.

턴다면 이번 index의 cost에다가 index+2 위치로 dp를 이어나가고 안턴다면 index+1 위치로 dp를 이어나간다.

 

다만 첫 집일때와 마지막 집일때의 예외처리를 해주었다.

첫 집일때는 stolenfirstHome = true 를 처리해주고,

마지막 집일때는 첫집이 안털린 경우에만(stolenFirstHome = false) 터는 것으로 해주었다.

#include <string>
#include <vector>
#include <string.h>

using namespace std;

int cache[1000000][2];
vector<int> MONEY;

int MONEY_COUNT;
int FIRST_HOME;
int LAST_HOME;

int dp(int index, bool stolenfirstHome) {
    if(index >= MONEY_COUNT) {
        return 0;
    }
    
    int& returnValue = cache[index][stolenfirstHome];

    if(returnValue != -1) {
        return returnValue;
    }
    
    if(index == FIRST_HOME) {
        returnValue = MONEY[index] + max(returnValue, dp(index + 2, true));
    } else if(index == LAST_HOME) {
        if(!stolenfirstHome) {
             returnValue = MONEY[index] + max(returnValue, dp(index + 2, stolenfirstHome));
        }
    } else {
        returnValue = MONEY[index] + max(returnValue, dp(index + 2, stolenfirstHome));
    }

    returnValue = max(returnValue, dp(index + 1,stolenfirstHome));

    return returnValue;
}

int solution(vector<int> money) {
    MONEY = money;

    MONEY_COUNT = money.size();
    FIRST_HOME = 0;
    LAST_HOME = MONEY_COUNT - 1;

    memset(cache, -1 , sizeof(cache));

    return dp(0, false);
}