[ 백트래킹 코드 ] - 시간초과
#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;
}
[ 정답 풀이 ] - 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)
을 사용해야 한다