★ [2] 땅따먹기 (DP, 완전탐색 X)

문제 설명
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,
| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |
로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.
마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항
행의 개수 N : 100,000 이하의 자연수
열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
점수 : 100 이하의 자연수

입출력 예
land answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]] 16
입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.

---

문제 풀이

DP 문제이다..

너무 오랜만에 DP라 감을 못잡아서 그냥 풀이방향 찾아보고 풀었다.

• 지금 이곳까지 내려오는데 가질 수 있는 최대값 = 지금 이곳의 값 + 이전행의 열까지 내려오는데 가질 수 있는 3 개의 최대값 중 최대갓

 

 

처음에 DFS로 완전탐색했지만 장렬히 시간초과..

 vector<vector<int>> vec;
 int answer = 0;
void DFS(int val, int depth, int lastStep)
{
	if (depth == vec.size() - 1)
	{
		answer = max(answer, val);
		return;
	}

	for (int i = 0; i < vec[depth + 1].size(); i++)
	{
		if (lastStep == i)
			continue;

		DFS(val + vec[depth + 1][i], depth + 1, i);
	}
}

 

정답 코드

int solution(vector<vector<int>> land)
{
	vector<vector<int>> dp(land.size(), vector<int>(4));
	int answer = 0;

	dp[0][0] = land[0][0];
	dp[0][1] = land[0][1];
	dp[0][2] = land[0][2];
	dp[0][3] = land[0][3];
	for (int i = 1; i < land.size(); i++)
	{
		dp[i][0] = land[i][0] + max(max(dp[i - 1][1], dp[i - 1][2]), dp[i - 1][3]);
		dp[i][1] = land[i][1] + max(max(dp[i - 1][0], dp[i - 1][2]), dp[i - 1][3]);
		dp[i][2] = land[i][2] + max(max(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][3]);
		dp[i][3] = land[i][3] + max(max(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]);
	}
	int last = land.size() - 1;
	answer = max(max(max(dp[last][0], dp[last][1]), dp[last][2]), dp[last][3]);

	return answer;
}