(c++)프로그래머스 코딩테스트 연습 - 도둑질

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

코딩테스트 연습 - 도둑질

[풀이]

DP로 풀어야 하는 문제였다.

첫번째 집과 마지막 집이 같이 선택되면 안되므로 첫번째 집을 선택하지 않는 경우와 첫번째 집을 선택하는 경우로 나누어서 풀어야한다.

#include <string>
#include <vector>
#include <algorithm>//max

using namespace std;

int *dp;
int house_cnt;

int DP(vector<int>money) {
	dp[0] = money[0];
    	//첫번째 집 안 고르면
	dp[1] = money[1];
	dp[2] = max(dp[1], money[2]);
	for (int i = 3; i < house_cnt; i++) {
		dp[i] = max(dp[i - 2] + money[i], dp[i - 1]);
	}
	int m = dp[house_cnt - 1];
	//첫번째 집 고르면
	dp[house_cnt - 2] = money[house_cnt - 2];
	dp[house_cnt - 3] = max(dp[house_cnt - 2], money[house_cnt - 3]);
	for (int i = house_cnt - 4; i >= 0; i--) {
		dp[i] = max(dp[i + 2] + money[i], dp[i + 1]);
	}
	m = max(m, dp[0]);
	return m;
}

int solution(vector<int> money) {
	int answer = 0;
	house_cnt = money.size();
	dp = new int[house_cnt];
	answer = DP(money);
	return answer;
}