[프로그래머스/알고리즘] 도둑질

문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

해결 방법

동그랗게 배치되어 있기 때문에 배열의 첫번째 집이 만약 훔친다면 마지막 집은 훔칠수 없습니다.

그리고 첫번째 값이 훔치지 않았다면 마지막 집을 훔칠 수 있습니다.

이 2가지 경우를 고려하면서 문제를 풀어나갔습니다.

인접한 집이 아닐 경우는 자신의 위치에서 1칸 띄거나 2칸 띌 수 있습니다. 이를 이용해서 동적계획으로 N번째의 집까지 훔칠 수 있는 돈의 최댓값을 하나하나 구하시면 됩니다.

소스 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> money) {
	int answer = 0;
	int cmax = 0;
	int temp = 0;
	vector<int> result(money.size() + 2);

	//1번째 경우
	result[2] = money[0];
	for (int i = 1; i < money.size()-1; i++) {
		if (result[i] + money[i] > result[i-1] + money[i]) {
			result[i + 2] = money[i] + result[i];
		}
		else {
			result[i + 2] = money[i] + result[i-1];
		}
		cmax = max(cmax, result[i + 2]);
	}
	//2번째 경우
	result.clear();
	result.assign(money.size() + 2, 0);
	result[3] = money[1];
	for (int i = 2; i < money.size(); i++) {
		if (result[i] + money[i] > result[i - 1] + money[i]) {
			result[i + 2] = money[i] + result[i];
		}
		else {
			result[i + 2] = money[i] + result[i-1];
		}
		cmax = max(cmax, result[i + 2]);
	}
	return cmax;
}