프로그래머스 도둑질

프로그래머스 코딩테스트 연습의 DP 분류 마지막 문제이다. 뭔가 어디서 봤던 문제같긴 한데, 다시 생각해봤다. 근데 되게 머리가 아팠다. DP배열을 쓰고 어디서부터 어디까지 최적해를 찾아본다 했지만, 앞에서부터 찾아봐도 뒤에서부터 찾아봐도 답이 없었다.

집이 원형이 아니고 직선 형태로 배치되어 있다면 해당 접근이 괜찮아 보이는데, 맨 앞 칸과 맨 뒤 칸이 조건에 맞물려 있어 답이 없어보였다.

 

이렇게 해볼까 저렇게 해볼까 고민을 하다가, 질문들을 찾아봤다. 그 중에, DFS와 섞은 솔루션이 있어서 찬찬히 뜯어보면서 답을 작성해봤다.

 

일단 dp[i][b] 는 , 첫번째 집을 털었거나(b==true), 털지 않았을 때(b==false) i번째 집까지 털었을 경우 최대값을 의미한다. 첫번째 집을 털었을 경우, 마지막 집을 털지 못하는 조건이 있기 때문에 두 가지 경우를 다르게 설정하고 접근을 한다.

그리고, DFS를 사용한다. 처음 집부터 시작해서, 한 집씩 들어가면서 현재 집을 선택했을때/선택하지 않았을 때 분기하면서 최대값을 찾아나가게 된다.

DFS 탈출 조건은, 인덱스가 N보다 커졌을 때와 마지막 집을 보는데 첫 집을 털었을 경우이다. 이 경우는 0을 리턴하며 DFS가 끝난다.

라인별로 설명을 해뒀다.

---

#include <iostream>
#include <vector>
#include <cstring>

using namespace  std;
const int MAX = 1000001;

int dp[MAX][2];
int n;
vector<int> g_money;

int dp_dfs(int house, bool first_select) // 다음집 or 다다음집 탐색하면서 값 찾아감 - DFS같다.
{
    if (house >= n) // 집 인덱스 초과 -> 0
        return (0);
    if (house == n-1 && first_select) //마지막 집을 보는데 첫집 선택? -> 0
        return (0);

    int &ret = dp[house][first_select]; // 현재 집 상태(초기선택 여부까지) 확인
    if (ret != -1) // 초기값이 아니면 그냥 리턴
        return ret;
    
    if (house == 0) // 현재 집이 처음 집이다? 이 선택이 기록되어야 함.
    {
        first_select = true; // 첫 집을 골랐을 경우
        ret = max(ret, g_money[house] + dp_dfs(house + 2, first_select)); 
        // first_select에 저장하고, 현재 집 값 + 다다음집 탐색 값과 ret 비교, 최대값 취함
        first_select = false; // 첫 집을 고르지 않았을 경우
        ret = max(ret, dp_dfs(house + 1, first_select));
        // first_select에 저장하고, 다음 집 값 탐색값과 ret 비교, 최대값 취함.
    }
    else
    {
        ret = max(ret, g_money[house] + dp_dfs(house + 2, first_select));
        // 현재 집 선택했을 경우 -> 현재 집 값 더하고 다다음 집 탐색
        ret = max(ret, dp_dfs(house + 1, first_select));
        // 현재 집 선택하지 않았을 경우 -> 다음 집부터 탐색
    }
    return (ret);
}

int solution(vector<int> money)
{
    n = money.size();
    g_money = money;
    memset(dp, -1, sizeof(dp));

    int answer = dp_dfs(0, false);

    return (answer);
}

 

DP와 DFS를 합쳐 구현한게 신기했다. 생각해보면, DP는 문제 과정을 저장한다/답의 부분최적해가 전체 최적해에 포함된다. 라는 개념으로 생각하고 있고, DFS는 그저 탐색 방법이니 둘을 섞는게 큰 문제가 없어보이긴 한다. DP, BFS, DFS... 같은 개념들을 언제든지 조합할 수 있다는 관념을 가질 필요가 있는 것 같다. 

 

오늘도 평온한 하루가 되길. 슨민.