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

도둑질

문제 설명

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

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

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

 

제한사항

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

입출력 예

 

money	return
[1, 2, 3, 1]	4

---

문제 자체는 간단하다. 연속되는 배열 원소와, 처음과 끝 원소를 동시에 선택하지 못하는 경우 중, 숫자가 가장 큰 최댓값을 찾아내는 동적계획법(DP) 문제이다.

 

문제를 풀이하기 위해선, 집을 선택하는 경우의 수를 나눠서 dp를 계산해야 한다.

집이 원형으로 배치되었기 때문에, 연속되는 집을 선택할 수 없으니 처음 집과 마지막 집은 반드시 동시에 선택될 수 없다.

따라서 경우의 수는 아래와 같이 두가지로 나뉜다.

1. 첫번째 집을 선택하는 경우 → 마지막 집을 선택하지 못함
2. 첫번째 집을 선택하지 않는 경우 → 마지막 집 선택하거나 or 안하거나

 

원형 조건때문에, 첫번째 집이나 마지막 집을 둘 중 하나 선택하는 경우로 나누면 틀린다.

첫번째 집을 선택하지 않는 경우에는 마지막 집을 선택하거나 선택하지 않을수도 있기 때문에 그 부분을 잘 생각해야 했다.

 

또한, 이 문제를 배열 2개로 나누어 풀이하는 방법과 for문을 2번 사용하는 방법으로 각각 구현할 수 있는데, 나는 우선 for문을 2번 사용하는 경우로 설명할 것이다.

 

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int dp[1000001];

// for문 2개 쓰는 버전
int solution(vector<int> money) {
	int answer = 0;

	// 첫번째 집을 방문하는 경우 => 마지막 집 방문 안함
	dp[0] = money[0];
	dp[1] = max(money[0], money[1]);

	for (int i = 2; i < money.size(); i++)
	{
		if (i == money.size() - 1) // 마지막 집 방문 X
		{
			dp[i] = dp[i - 1];
			continue;
		}
		dp[i] = max(dp[i - 2] + money[i], dp[i - 1]);
	}

	answer = dp[money.size() - 1];

	// 첫번째 집을 방문하지 않는 경우 => 마지막 집은 방문 할수도 있고, 안할수도 있고
	dp[0] = 0;
	dp[1] = money[1];
	for (int i = 2; i < money.size(); i++)
		dp[i] = max(dp[i - 2] + money[i], dp[i - 1]);

	answer = max(answer, dp[money.size() - 1]);

	return answer;
}

 

dp 배열을 집의 최대 갯수만큼 선언하고 몇번째 집까지 왔을 때 얼마를 훔쳤는지를 원소로 저장하였다.

 

📌 첫번째 집을 방문하는 경우

첫번째 집을 방문하는 경우엔 마지막 집을 무조건 방문하지 않는다. 따라서, dp[0]은 첫번째 집의 원소 값 money[0]로 초기화하고, dp[1]은 첫번째랑 두번째 집 중 더 큰 값으로 초기화하였다.

 

마지막 집을 방문하지 않으므로 for문을 돌릴 때 i == money.size() - 1 인 경우엔 dp값을 마지막에서 하나 이전 집(dp[i-1])까지만 방문한 값을 그대로 저장해준다.

 

📌 첫번째 집을 방문하지 않는 경우

첫번째 집을 방문하지 않는 경우엔 dp[0] 값을 0으로 초기화한다. 따라서 dp[1]도 첫번째랑 두번째 집을 비교하는게 아니라 첫번째 집에서 시작하는걸로 고정한다. (dp[1] = money[1])

 

for문은 차례로 돌면서 2번째 이전에 위치한 집에 현재 집 돈을 합친 금액과, 그냥 첫번째 이전 집만 선택한 금액을 비교하여 더 큰 값을 저장한다.

즉, 현재 집을 선택하지 않고 이전 집까지 훔친 돈이랑, 현재 집에서도 돈을 훔치고 인접하지 않은 집에서 훔친것까지 합친 돈 중에 뭐가 더 큰지를 비교하는 것이다.

 

두 가지 경우의 수를 모두 비교하였으면 더 큰 결과 값을 return 해준다.

---

같은 풀이지만, 배열을 2가지로 나누어 풀이하는 방법도 있다.

이땐, 주어진 돈 배열 money를 앞과 뒤로 하나씩 잘라 두개의 배열로 만든다. 즉, 배열 자체를 첫번째 집과 마지막 집이 동시에 선택될 수 없도록 개조하는 것이다.

 

[10,20,30,40] 이라는 money 배열이 있다면, [10,20,30] 배열과 [20,30,40] 배열로 나누고, 0번째 인덱스에 0을 추가하여 전체 집의 개수를 맞춰준다.

따라서 dp로 비교하는 배열은 [0,10,20,30], [0,20,30,40] 로 만들어져 사용되는 것이다.

 

dp 점화식 자체는 위에 방법이랑 동일하므로 다른 설명 없이 코드만 첨부하도록 하였다.

 

> 코드

// 배열 2개 쓰는 버전
int solution(vector<int> money) {
	vector<int> one(money.size(), money[0]), two(money.size(), money[1]);
	vector<int> m1(money.begin()+1, money.end());
	m1.insert(m1.begin(), 0);
		
	vector<int> m2(money.begin(), money.end()-1);
	m2.insert(m2.begin(), 0);

	vector<int> dp1(m1.size() + 1);
	dp1[1] = m1[0];
	dp1[2] = m1[1];

	vector<int> dp2(money.size() + 1);
	dp2[1] = m2[0];
	dp2[2] = m2[1];

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

	return max(dp1[money.size()], dp2[money.size()]);
}

---

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

프로그래머스