[java] 프로그래머스 - 땅따먹기

문제

프로그래머스-땅따먹기

주어진 게임판에서 각 행의 4칸 중 한칸만 밟으면서 내려올 때 얻을 수 있는 최고점을 찾는 문제.
단, 한 행씩 내려올때, 같은 열을 연속해서 밟을 수 없는 규칙이 있다.

• 예시

0 : | 1 | 2 | 3 | 5 |
1 : | 5 | 6 | 7 | 8 |
2 : | 4 | 3 | 2 | 1 |

0행의 네번째 칸, 1행의 세번째 칸, 2행의 첫번째 칸을 밟을 때의 경우, 16점이 최고점이다.
(5) + (7) + (4) = 16
(5)를 밟은 경우, 규칙에 의해 (8)은 밟을 수 없음

풀이

각 칸에서 얻을 수 있는 최고점을 저장하는 정수 배열 memo를 사용했다.
memo배열의 초기값은 가장 마지막 행을 제외한 칸에Integer.MIN_VALUE를 저장했다

행의 갯수가 n개라면 n-1행부터 0행까지 역으로 반복문을 돌았다.
해당 차례의 행에서 열을 반복하며 같은 열이 아닌 아래행 값 중 내가 가진 칸의 값을 합했을때 가장 큰 값을 저장했다.

반복 수행 후 가장 상단의 열의 값 중 큰 값을 리턴한다.

주어진 배열(land)이 다음과 같을 경우,

| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |

memo배열은 다음과 같은 초기값을 가진다.

       0열   1열  2열  3열
0행 : | -M | -M | -M | -M |
1행 : | -M | -M | -M | -M |
2행 : |  4 |  3 |  2 |  1 |

1행의 0열부터 3열까지 반복하며 현재 칸의 land값과 2행의 4개 열 중 더했을 때 가장 큰 값을 memo자리에 저장한다.

• 1행의 0열의 경우,
  land[1][0]은 5
  2행의 4개 열 중 0열이 아니며 큰 값은 land[2][1]인 3
  memo[1][0]은 8을 저장한다.

1행 결과

       0열   1열  2열  3열
0행 : | -M | -M | -M | -M |
1행 : |  8 | 10 | 11 | 12 |
2행 : |  4 |  3 |  2 |  1 |

2행 결과

       0열   1열  2열  3열
0행 : | 13 | 14 | 15 | 16 |
1행 : |  8 | 10 | 11 | 12 |
2행 : |  4 |  3 |  2 |  1 |

memo배열의 0행 중 가장 큰 값이 정답

소스코드

import java.util.Arrays;
class Solution {
    	static int solution(int[][] land) {
		int memo[][];
		int answer = 0;
		memo = new int[land.length][4];
		for (int i = 0; i < memo.length - 1; i++) {
			Arrays.fill(memo[i], Integer.MIN_VALUE);
		}
		memo[memo.length - 1] = land[land.length - 1];

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