땅따먹기

코드

[ 백트래킹 코드 ] - 시간초과

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int ans,N;
vector<int> arr;
vector<vector<int>> val;
void func(int depth, int start, int prev)
{
    int tot=0;
    if(depth == N){
        for(int i=0;i<N;i++)
            tot += arr[i];
        ans=max(ans,tot);
    }else{
        for(int i=start;i<N;i++)
        {
            for(int j=0;j<4;j++)
            {
                if(prev == j) continue;
                arr[depth] = val[i][j];
                func(depth+1, i+1, j);
            }
        }
    }
}
int solution(vector<vector<int>> land)
{
    int answer = 0;
    N = land.size();
    arr.resize(N);
    val.resize(N);
    for(int i=0;i<N;i++)
        for(int j=0;j<4;j++)
            val[i].push_back(land[i][j]);
    func(0, 0, -1);
    answer = ans;
    return answer;
}

• 문제
  : N이 너무 커서 시간초과

---

[ 정답 풀이 ] - DP

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int d[100003][4];
int solution(vector<vector<int>> land)
{
    int answer = 0;int N = land.size();
    d[0][0] = land[0][0];d[0][1] = land[0][1];
    d[0][2] = land[0][2];d[0][3] = land[0][3];
    for(int i=1;i<N;i++)
    {
        d[i][0] = max(d[i-1][1], max(d[i-1][2], d[i-1][3])) + land[i][0];
        d[i][1] = max(d[i-1][0], max(d[i-1][2], d[i-1][3])) + land[i][1];
        d[i][2] = max(d[i-1][0], max(d[i-1][1], d[i-1][3])) + land[i][2];
        d[i][3] = max(d[i-1][0], max(d[i-1][1], d[i-1][2])) + land[i][3];
    }
    answer = max(d[N-1][0], max(d[N-1][1], max(d[N-1][2], d[N-1][3])));
    return answer;
}

• key point!
  : DP의 핵심인 메모제이션(memoization)을 사용해야 한다