[프로그래머스] 도둑질

링크

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

프로그래머스

풀이

인접한 집에서 도둑이 훔칠 수 있는 돈의 최댓값을 구하는 문제이다.

 

일단 원형으로 이루어진 집을 일렬로 쫙 나열해보면

이렇게 나타 낼 수 있는데 이때 3번째 2를 도착하기 위해서는 2가지 방법이 있다.

1. 첫 번째 집에서 10을 훔치고 세 번째 2에 도착하여 2를 훔치기

2. 두 번째 집에서 2를 훔치고 세 번째 2에 도착하여 2을 훔치지 않기

 

그렇다면 이를 이용하여 훔친 돈의 최댓값 dp 점화식을 세울 수 있는데

dp [현재 위치] = max(dp[현재 위치 -1] , dp[현재 위치 - 2] + money [현재 위치])

 

하지만 위의 식으로만 답을 구할 수는 없다.

왜냐하면 집은 원형으로 이어져 있어 첫 번째 10과 마지막 2를 동시에 훔칠 수는 없기 때문이다.

 

그래서 두 개의 조건을 통하여 dp배열을 2개를 만들었는데

1. 첫 번째 집을 훔치고 마지막 집을 훔치지 않았을 때

2. 첫 번째 집을 훔치지 않고 마지막 집을 훔쳤을 때

 

두 개의 dp 배열을 완성한 후 비교하여 최댓값을 구할 수 있었다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 1010000
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

int dp1[SIZE];
int dp2[SIZE];
int solution(vector<int> money) {
	int answer = 0;

	//집이 3개 일때
	if (money.size() == 3)
		return (money[1] > money[0] + money[2] ? money[1] : money[0] + money[2]);
	//시계방향부터 1번 시작
	
	//1번을 훔치고 마지막 집을 안 훔칠 때
	dp1[0] = money[0]; dp1[1] = max(money[0],money[1]);

	for (int i = 2; i < money.size() - 1; i++) {
		dp1[i] = max(dp1[i - 1], dp1[i - 2] + money[i]);
	}

	//1번 안 훔치고 마지막 집을 훔칠 때
	dp2[0] = 0; dp2[1] = money[1];
	for (int i = 2; i < money.size(); i++) {
		dp2[i] = max(dp2[i - 1], dp2[i - 2] + money[i]);
	}

	//최대값 도출
	for (int i = 0; i < money.size(); i++) {
		answer = max(answer, max(dp1[i], dp2[i]));
	}

	return answer;
}