[프로그래머스] 도둑질

문제 설명

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

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

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

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력 예

moneyreturn

[1, 2, 3, 1]

4

---

원형의 집에서 최대 값을 구하는 문제이다.

원형이기 때문에 첫번째 집을 선택하느냐 안 하느냐가 중요한 문제이다.

첫번째 집을 선택하면 마지막 집을 선택할 수 없기 때문이다. 

따라서 두 경우를 위해 따로 dp 배열을 생성한다.

dp는 첫번째 집부터 선택한 경우이고, dp2는 두번째 집부터 선택하는 경우이다.

배열을 그렇게 설정했다면 점화식은 어렵지 않다.

dp[i] = max(dp[i-2]+m[i], dp[i-1])이다. 즉 현재-2번째 집과 현재집을 선택한 것과 현재-1번째 집 중에서 더 큰 값을 구한다. 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Programmers/%EB%8F%84%EB%91%91%EC%A7%88.cpp

chosh95/STUDY

C++ 코드

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

int dp[1000001];
int dp2[1000001];

int solution(vector<int> money) {
	int res = 0;
	int n = money.size() - 1;
	dp[0] = money[0];
	dp[1] = money[0];
	dp2[0] = 0;
	dp2[1] = money[1];

	for (int i = 2; i < n; i++) {
		dp[i] = max(dp[i - 2] + money[i], dp[i - 1]);
		dp2[i] = max(dp2[i - 2] + money[i], dp2[i - 1]);
	}
	dp2[n] = max(dp2[n - 2] + money[n], dp2[n - 1]);

	return res = max(dp[n - 1], dp2[n]);
}

int main()
{
	cout << solution({ 1,2,3,1 });
}