Problem 문제풀이
DP를 조금 변형한 문제이다. 백준에서 색칠하는 문제 중에 이와 비슷한 문제가 있었던 것으로 기억한다.
문제 설명을 간단히 하자면 원형으로 집이 있는 마을에서 도둑질을 할 것인데 인접한 집은 털 수 없다.
가장 큰 이익을 얻으려면 어떻게 해야하는지 묻는 문제이다.
문제 자체는 쉽지만 처음과 끝이 이웃이라는게 조금 골치아프다. 여러 방법이 있겠지만
그냥 DP를 두 번 돌리는 방식으로 문제를 해결하였다.
-
DP를 초기화해주고 2가지 경우로 문제를 나눈다.
-
첫 번째 집을 털지 않았을 경우의 최대 해를 구한다.
-
첫 번째 집을 털었을 경우의 최대 해를 구한다.
-
-
Solution은 간단하다. 우선 어떤 상황이든 이번 집에서 도둑질을 할 경우와 하지 않을 경우로 나뉜다.
-
도둑질을 했을 경우 다음 집에서 도둑질을 하지 못하기 때문에 돈을 챙겨서 2집을 건너간다.
-
안 했을경우 빈 손으로 다음 집으로 간다.
-
-
최대 이익을 구했으면 마지막 집을 삭제하고 1-2 가정으로 문제를 푼다.
1.
for(int i=0;i<1000001;i++)
{
DP[i]=-1;
}
2.
int solve(int stage)
{
if (stage + 2 >= money.size())
{
if (stage + 1 < money.size()) //제일 마지막 2집이 남았을 경우 둘 중 부잣집을 터는게 이익이다(음흉...)
{
return max(money[stage], money[stage+1]);
}
return money[stage]; //아쉬운대로 남은 한 집이라도 턴다.
}
int& res = DP[stage];
if (res != -1)
{
return res;
}
res = money[stage] + solve(stage + 2); //도둑질을 할 것인가?
res = max(res, solve(stage + 1)); //양심의 가책을 느끼고 넘어갈 것인가?
return res;
}
3.
for(int i=0;i<1000001;i++) //첫 번째 집을 안 털었다는 전제로 DP를 만들었기 때문에 초기화가 필요하다.
{
DP[i]=-1;
}
money.pop_back(); //첫 번째 집을 털면 마지막 집은 못 털게 된다.
answer = max(answer, solve(0));
4.
for(int i=0;i<a_size;i++)
{
if(res[i])
{
answer++;
}
}
return answer;
평범한 DP문제인데 오랜만에 풀다보니 너무 헤맸다.
여러분한테는 DP는 껌이기 때문에 걱정할 필요 없겠지만? ㅎㅎ 전체 코드를 남기며 마무리한다.
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> money;
int DP[1000001];
int solve(int stage);
int solution(vector<int> _money) {
int answer = 0;
money = _money;
for(int i=0;i<1000001;i++)
{
DP[i]=-1;
}
answer = solve(1);
for(int i=0;i<1000001;i++)
{
DP[i]=-1;
}
money.pop_back();
answer = max(answer, solve(0));
return answer;
}
int solve(int stage)
{
if (stage + 2 >= money.size())
{
if (stage + 1 < money.size())
{
return max(money[stage], money[stage+1]);
}
return money[stage];
}
int& res = DP[stage];
if (res != -1)
{
return res;
}
res = money[stage] + solve(stage + 2);
res = max(res, solve(stage + 1));
return res;
}