프로그래머스 도둑질 문제 풀이를 진행하였습니다.
문제 해석
문제를 읽으면 아래와 같은 해석이 가능합니다.
모든 집이 동그랗게 배치된 마을이 있습니다.
도둑이 집을 터는데 서로 인접한 두 집을 털면 경보가 울리게 됩니다.
집에 있는 돈이 순서대로 나열된 배열을 가지고 경보가 울리지 않고 제일 많은 돈을 훔쳐야합니다.
문제 풀이
제한사항이 매우 크기 때문에 하나씩 검색하는 방법은 시간초과가 나옵니다.
그러니 문제에 맞는 점화식을 찾을 것입니다.
주어진 배열 [1,2,3,1,5]로 문제를 보면
첫번째 집만 훔쳤을 때 제일 많은 돈은 한 집 뿐이므로 1입니다.
두번째 집까지 훔쳤을 때 제일 많은 돈은 1번째와 2번째 집 중 한곳만 훔칠 수 있으므로 둘 중 큰 값인 2입니다.
세번재 집까지 훔쳤을 때 제일 많은 돈은 1번째와 3번째를 훔치거나 2번째만 훔치는 경우가 있으므로 큰 값인 4입니다.
네번재 집까지 훔쳤을 때 제일 많은 돈은 2번째 집까지 훔쳤을 때의 최대값과 현재 집까지 훔친 값과 3번째 집까지 훔치는 경우가 있으므로 4입니다.
이런식으로 집을 계산한다고 하였을 때 점화식은 전에 훔쳤던 집의 최대값과 전전에 훔쳤던 집의 최대값+현재 집의 훔칠 돈의 값을 비교하여 더 큰 값이 현재 집까지 훔쳤을 때 나올 수 있는 최대값이 됩니다.
즉 index의 집의 최대값 = 전집의 최대값과 (전전집의 최대값+현재 집의 값)중 최대값이 됩니다.
여기서 한 가지 더 생각해야 되는 부분은 모든 집이 동그랗게 되어 있기 때문에 시작 집과 끝 집이 붙어 있다는 것입니다.
첫번째 집을 훔쳤을 경우 마지막집을 훔칠 수 없으며 마지막 집을 훔쳤을 경우 첫번째 집을 훔칠 수 없습니다.
이를 간단하게 해결하는 방법은 마지막 집의 값을 빼고 계산하는 경우와, 첫번째 집의 값을 빼고 계산하는 경우를 둘 다 계산하여 값이 큰 쪽을 답으로 제출하는 방법이 있습니다.
즉 [1,2,3,1,5]로 보면 [1,2,3,1,0], [0,2,3,1,5] 두 개의 배열로 계산하여 더 큰 값을 찾아주면 됩니다.
계산을 편하게 하기 위하여 [0,1,2,3,1], [0,2,3,1,5] 로 계산하면 됩니다.
전체 코드
#include <bits/stdc++.h>
#include <string>
#include <vector>
using namespace std;
int solution(vector<int> money) {
int answer = 0;
vector<int> dp1(1000001, 0); //첫번째 원소를 포함하고 마지막 원소를 제외한 값
vector<int> dp2(1000001, 0); //첫번째 원소를 제외하고 마지막 원소를 포함한 값
dp1[0] = 0;
dp1[1] = money[0];
dp1[2] = max(money[1], money[0]);
dp2[0] = 0;
dp2[1] = money[1];
dp2[2] = max(money[1], money[2]);
//index의 집의 최대값 = 전집의 최대값과 (전전집의 최대값+현재 집의 값)중 최대값
for(int i = 3; i < money.size(); i++)
{
dp1[i] = max(dp1[i-1], dp1[i-2] + money[i-1]);
dp2[i] = max(dp2[i-1], dp2[i-2] + money[i]);
}
answer = max(dp1[money.size()-1], dp2[money.size()-1]);
return answer;
}출저
https://school.programmers.co.kr/learn/courses/30/lessons/42897
