[동적계획법, 난이도 중상] 프로그래머즈, 도둑질

Programmers의 문제들은 난이도별로 다섯 레벨로 나뉘는데, 그 중 Level 4에 속하는 난이도 있는 문제이다. 

그래도 백준에서 DP를 50문제 넘게 푼 짬이 있어서 그런지 크게 어렵지는 않았다.

 

집이 일렬로 있는게 아니라 원형으로 배치 되어있기 때문에 접근법을 좀 다르게 생각해줘야 한다.

결론부터 말하자면 3가지 경우에 대해 DP를 수행하여 이들 중 최댓값을 구하면 된다.

3가지 경우는 이렇다.

• 0번째 집부터 터는 경우
• 1번째 집부터 터는 경우
• 2번째 집부터 터는 경우

3번째 집부터 터는 경우는 1번째 집을 털 수 있는 상황인데도 털지 않는 경우이므로 최대값이 나올 일이 없다.

케이스별로 DP수행 직전 상황을 그림으로 간략하게 표현하였는데, 회색은 털 수 없는 집이다.

 

1. 0번째 집부터 터는 경우 - DP를 수행할 때 n-1번째 집은 포함하지 않게 예외 처리를 해주면 된다.

 

2. 1번째 집부터 터는 경우 - 특별히 신경 써야 하는 것은 없다.

 

3. 2번째 집부터 터는 경우 - 2번째 집부터 터는 것이니 0번째 집도 열외한다. 

 

이렇게 케이스별로 DP를 수행하는데

케이스별로 3가지 상황이 나올 수 있다.

• i-3번째 집까지 털고 i번째 집을 터는 경우
• i-2번째 집까지 털고 i번째 집을 터는 경우
• i-1번째 집까지 털고 i번째 집은 털지 않는 경우

물론 여기서 i-j 번째 집까지 털었다는 의미는 0번째 집부터 문제 규칙에 맞게 털었다는 것이지

0번째 집부터 i-j 번째 집까지 i-j+1채의 집을 전부 털었다는 의미가 아니다.

 

이 3가지 상황중 최대로 많이 훔칠 수 있는 금액이 DP값이 되는 것이다.

 

이렇게 0,1,2번째 집부터 터는 3가지 케이스에 대한 각각의 DP를 수행해주고, 각 n-1번째 집에서의 DP값들중 최댓값을 구하면 문제가 해결 된다.

 

#include <vector>
using namespace std;
int dp0[1000001]; //0번째 집부터 터는 경우
int dp1[1000001]; //1번째 집부터 터는 경우
int dp2[1000001]; //2번째 집부터 터는 경우

int solution(vector<int> money) {
    int answer = 0;
    
    dp0[0]=money[0];
    dp0[1]=dp0[0];
    if(money.size()!=3) dp0[2]=dp0[0]+money[2]; 
    
    dp1[1]=money[1];
    dp1[2]=dp1[1];
    
    dp2[2]=money[2];
    
    for(int i=3;i<money.size();i++){
        if(i!=money.size()-1) dp0[i] = max(max(dp0[i-2]+money[i],dp0[i-3]+money[i]),dp0[i-1]);
        else dp0[i]=dp0[i-1];
        dp1[i] = max(max(dp1[i-2]+money[i],dp1[i-3]+money[i]),dp1[i-1]);
        dp2[i] = max(max(dp2[i-2]+money[i],dp2[i-3]+money[i]),dp2[i-1]);
    }
    
    answer = max(max(dp0[money.size()-1], dp1[money.size()-1]), dp2[money.size()-1]);
    return answer;
}