[프로그래머스/C++] 도둑질
1. 문제
도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.
각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.
2. 제한사항
- 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
- money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.
3. 풀이
(첫번째 항 포함, 마지막 항 미포함)과(첫번째 항 미포함, 마지막 항 포함)으로 DP 두 번 돌려서 최댓값 고르면 된다.- 원형만 아니면 흔한 DP 문제다.
- 원형이 아닐 때 점화식은
D[i] = max(D[i-2] +arr[i], D[i-1) - 최근에 DP 문제를 많이 풀어서 익숙해졌다.
- 저 점화식을 활용하되, 처음과 끝을 붙이면 안 된다는 조건만 만족시켜주면 된다.
- 다양한 방법을 생각해보았다.
- 첫번째 항을 가장 뒤에 붙이기
- bool 배열을 하나 만들어서 첫번째 항을 포함했는지 안 했는지 확인하기
- 근데 어차피 처음이랑 마지막만 신경쓰면 되니까 DP를 두 번 돌리는 것도 괜찮을 것 같았다.
- 시간 자체는 늘어나지만 big-O가 바뀌지는 않으니까 가능할 것 같았다.
4. 처음 코드와 달라진 점
- 딱히 없다.
- 머리 속으로 생각만 하다 코드를 좀 늦게 짰는데 그 코드가 바로 통과됐다.
- 다 풀고 생각해봤는데 배열 두 개까지 필요없고 하나만 있으면 될 것 같다.
추가했다. - 처음으로 푼 4단계 문제인데 생각보다 쉽게 풀렸다.
근데 제일 앞에 나오는 3단계 DP는 아직 못 풀었다.DP가 들어가면 일단 난이도가 높게 나오는 것 같다. - 3단계 이상은 잘 안 풀어봤는데 DP라서 그런건지 단계가 높아서 그런지는 몰라도 효율성 테스트가 꼭 있었다. DP라 그런 것 같기도 하다.
5-1. 코드(배열 2개)
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int dp1[1000000];
int dp2[1000001];
int solution(vector<int> money) {
int len = money.size();
dp1[0] = money[0];
dp1[1] = max(money[0], money[1]);
for(int i=2; i<len-1; i++){
dp1[i] = max(dp1[i-2]+money[i], dp1[i-1]);
}
dp2[1] = money[1];
for(int i=2; i<len; i++){
dp2[i] = max(dp2[i-2]+money[i], dp2[i-1]);
}
return max(dp1[len-2], dp2[len-1]);
}5-2. 코드(배열 1개)
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int dp[1000000];
int solution(vector<int> money) {
int answer;
int len = money.size();
dp[0] = money[0];
dp[1] = max(money[0], money[1]);
for(int i=2; i<len-1; i++){
dp[i] = max(dp[i-2]+money[i], dp[i-1]);
}
answer = dp[len-2];
dp[0] = 0;
dp[1] = money[1];
for(int i=2; i<len; i++){
dp[i] = max(dp[i-2]+money[i], dp[i-1]);
}
answer = max(answer, dp[len-1]);
return answer;
}