dp로 쉽게 풀 수 있는 문제.
N의 범위가 최대 100000이기 때문에 BFS로는 힘들 것 같아 DP를 생각했다.
dp[i][j]를 i-1행에서 j번째 땅을 택했을 때의 MAX값으로 정의하자. 그러면 i번째 행에서는 i-1행에서와 같은 열의 땅을 따 먹을 수 없으므로 나머지 세 땅 중에서 택할 수 있다.
문제에서 MAX값을 찾기 때문에 세 땅 중에서 현재까지 누적값이 가장 큰 행을 택해 그 땅을 따먹으면 된다.
#include <iostream>
#include <vector>
#define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))
#define THREE(X, Y, Z) MAX(MAX(X, Y), Z)
using namespace std;
int solution(vector<vector<int> > land)
{
int answer = 0;
int N = land.size();
int i;
int ** dp = new int *[N]; // dp[i][j]: i-1행에서 j번째 땅을 택했을 때의 MAX
for (i = 0; i < N; i++) dp[i] = new int[4];
for (i = 0; i < 4; i++) dp[0][i] = land[0][i];
for (i = 1; i < N; i++) {
dp[i][0] = THREE(dp[i - 1][1], dp[i - 1][2], dp[i - 1][3]) + land[i][0];
dp[i][1] = THREE(dp[i - 1][0], dp[i - 1][2], dp[i - 1][3]) + land[i][1];
dp[i][2] = THREE(dp[i - 1][0], dp[i - 1][1], dp[i - 1][3]) + land[i][2];
dp[i][3] = THREE(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]) + land[i][3];
}
answer = MAX(MAX(dp[N - 1][0], dp[N - 1][1]), MAX(dp[N - 1][2], dp[N - 1][3]));
return answer;
}