문제 설명
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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는 다른 말로 기억 알고리즘이라고도 불린다고 한다. 즉, 이전 값들을 임시값에 저장해나가며 앞으로 구할 값들을 임시값에 저장된 값들을 활용하여 푸는 문제이다.
이번 문제의 풀이 과정은 다음과 같다.
-
우선 임시 배열
d[0][i]에land[0][i]값을 담아준다.| 1 | 2 | 3 | 5 | 이와 같은 배열이 만들어진다.
-
그다음
d[1][0]부터d[1][3]까지 모든 숫자들을d[0]에 위치한 숫자들에 더해보며 최대값을 찾아나간다. (같은 열을 밟을 수 없기 때문에 인덱스가 같은 경우 continue 해준다.)| 1 | 2 | 3 | 5 |
|10|
→
d[1][1]값이 반복문을 통해d[0][0]부터d[0][3]까지의 숫자들과 더해지며, 두 수를 더했을 때 최대값이 되는 경우가d[1][1]이 되며, 이 과정을 반복해준다.| 1 | 2 | 3 | 5 |
|10|11|12|11|
→
| 1 | 2 | 3 | 5 |
|10|11|12|11|
|16|15|12|12|
연산을 마무리하면 위와같은 이차원 배열을 얻을 수 있고, 마지막줄의 최대값인 16을 return하면 정답이 된다.
class Solution {
int solution(int[][] land) {
int answer = 0;
int[][] d = new int[land.length][land[0].length];
for (int i = 0; i < 4; i++) {
d[0][i] = land[0][i];
}
for (int i = 1; i < land.length; i++) {
for (int j = 0; j < land[i].length; j++) {
for (int k = 0; k < land[i].length; k++) {
if (j==k) continue;
d[i][j] = Math.max(d[i][j], d[i - 1][k] + land[i][j]);
}
}
}
int max = 0;
for (int i = 0; i < d[0].length; i++) {
max = Math.max(max, d[d.length - 1][i]);
}
answer = max;
return answer;
}
}