[프로그래머스] 땅따먹기 (Java)

 

문제

프로그래머스

 

알고리즘

다이나믹 프로그래밍(DP)

 

풀이

i행 j열을 밟았을 때 점수의 최댓값은

i-1행에서 j열을 제외한 세 행을 밟았을 때 점수의 최댓값 + i행 j열의 점수이다.

예를 들여 3행 2열을 밟았을 때 점수의 최댓값은 2행 1열, 2행 3열, 2행 4열을 밟았을 때 점수의 최댓값 + 3행 2열의 점수이다.

 

따라서 다이나믹 프로그래밍으로 각 칸까지 얻을 수 있는 최댓값을 구하고, 마지막 행의 네 열 중 최댓값을 반환한다.

 

코드

class Solution {
	int solution(int[][] land) {
		int[][] dp = new int[land.length + 1][4];
		for (int i = 0; i < 4; i++)
			dp[0][i] = land[0][i];

		for (int i = 1; i < land.length; i++) {
			for (int j = 0; j < 4; j++) {
				int max = 0;
                
				for (int k = 0; k < 4; k++) {
					if (j == k) continue;
					max = Math.max(max, dp[i - 1][k]);
				}
				dp[i][j] = max + land[i][j];
			}
		}

		int max = 0;
		for (int k = 0; k < 4; k++)
			max = Math.max(max, dp[land.length - 1][k]);

		return max;
	}
}